单链表的删除
- 直接删除即可
- 删除后要
free
//删除第i个位置的元素
//删除时L是不会变的,所以不需要加引用
bool ListDelect(LinkList L,int i)
{//i = 1,即删除头指针//拿到要删除结点的前一个结点LinkList p= GetElem(L,i-1);if(NULL==p){return false;}//拿到要删除的结点指针LinkList q=p->next;//当链表只有5个结点,删除第6个结点,出现这种异常情况时,避免程序崩溃if(NULL==q){return false;}//断链p->next=q->next;//释放被删除结点的空间free(q);return true;
}
练习
设线性表L=(a1,a2,a4,…,an),采用带头结点的单链表存储,设计一个空间复杂度为O(1)且时间上尽可能高效的算法,重新排列L中的各结点,得到线性表L=(a1,an,a2,an-1…)
分析:
- 空间复杂度是O(1),我们不能申请额外的空间
- 找到链表的中间结点,前面一半是链表 L
- 将链表的后半部分给一个新的头结点 L2
- 然后将链表 L2 进行原地逆置
- 再将 L 和 L2 链表进行合并
问题一:如何找到链表的中间结点
- 如果首先遍历一次链表,长度假如是20,再次遍历走到第10个,这样的缺点是遍历了两次链表。
- 更好的办法:双指针法,两个指针同步向后遍历的方法。
- 定义两个指针
pcur
,ppre
,让pcur
指针每次走两步,
ppre
指针每次走一步,这样当pcur
指针走到最后,那么ppre
指针刚好在中间。- 注意,由于
pcur
每次循环是走两步的,因此每走一步都注意判断是否为NULL
。- 画图证明,无论奇数还是偶数,都可实现
- 把前一个列表的元素放多1个更方便,但是其实哪个多都一样
问题二: 后一半链表设置为L2,如何让L2原地转置
- 以上步骤循环往复,直到t为NULL时,结束循环
- 这时s是最后一个结点,r是倒数第二个结点,需要再
次执行一下s->next=r
- 最后需要
L2->next->next=NULL;
因为原有链表的头结点变成链表最后一个结点, 最后一个结点的next需要为NULL,这时让L2指向s,因为s是原链表最后一个结点- 完成了逆置后,就是第一个结点,因此链表头结点L2指向s。
问题三:L和L2链表合并,轮流放结点
- 因为空间复杂度是O(1),不申请新空间,需要3个指针
pcur,p,q
- 合并后的新链表让
pcur
指针始终指向新链表尾部,初始化为pcur=L->next
,使用p
指针始终指向链表L
待放入的结点,初始化值为p=L2->next
q
指针始终指向链表L2
待放入的结点,初始化值为q=L2->next
- 因为链表
L
的第一个结点不动,所以p=p->next
- 开启循环,循环结束后,有可能
L
还剩余一个结点,也可能L2
剩余一个结点,但是只会有一个剩余的有结点- 因此判断p不为NULL,把p放入,如果q不为NULL,把q放入即可。