C语言实题讲解快速掌握单链表上

第C语言实题讲解快速掌握单链表上目录1、移除链表元素2、反转链表3、链表的中间节点4、链表中倒数第k个节点5、合并两个有序链表6、链表分割

1、移除链表元素

链接直达：

移除链表元素

题目：

思路：

此题要综合考虑多种情况，常规情况就如同示例1，有多个节点，并且val不连续，但是非常规呢？当val连续呢？当头部就是val呢？所以要分类讨论

常规情况：

需要定义两个指针prev和cur，cur指向第一个数据，prev指向cur的前一个。依次遍历cur指向的数据是否为val，若是，则把prev的下一个节点指向cur的下一个节点上，cur=cur-next，prev跟着cur一起走，直到cur走到NULL

连续val：

当我们仔细观察下，不难发现，在常规情况下是可以解决连续val的，但是头部val就不可了

头部val：

此时除了刚才定义的两个指针prev和cur外，还要有个head指向头部，当头部是val时，将cur指向下一个位置，head跟着一起动，直到cur指向的数据不为val时，将head赋给prev。此时剩余的就按常规处理即可。

代码如下：

structListNode*removeElements(structListNode*head,intval){

structListNode*cur=head;

structListNode*prev=NULL;

while(cur)

if(cur-val!=val)

prev=cur;

cur=cur-next;

else

structListNode*next=cur-next;

if(prev==NULL)

free(cur);

cur=next;

head=next;

else

prev-next=cur-next;

free(cur);

cur=prev-next;

returnhead;

}

2、反转链表

链接直达：

反转链表

题目：

思路：

法一：三指针翻转方向

定义三个指针n1，n2，n3分别用来指向NULL，第一个数据，第二个数据。让n2的next指向n1，把n2赋给n1，再把n3赋给n2，再执行n3=n3-next的操作，接下来重复上述操作，直到n2指向空即可。但是要注意，要先判断该链表是否为NULL，如果是，则返回NULL，此外，还要保证当n3为空时就不要动了，直接把n3赋给n2即可。

代码如下：

structListNode*reverseList(structListNode*head){

if(head==NULL)

returnNULL;

structListNode*n1=NULL;

structListNode*n2=head;

structListNode*n3=n2-next;

while(n2)

n2-next=n1;

n1=n2;

n2=n3;

if(n3)

n3=n3-next;

returnn1;

}

法二：头插

此法就需要再创建一个链表了，创建一个新的头部newhead指向NULL，再定义一个指针cur指向原链表第一个数据，注意还得定义一个指针next指向cur的下一个节点。遍历原链表，把节点取下来头插到newhead所在的链表。每次更新newhead赋给cur，如图所示：

代码如下：

structListNode*reverseList(structListNode*head){

if(head==NULL)

returnNULL;

structListNode*cur=head;

structListNode*next=cur-next;

structListNode*newhead=NULL;

while(cur)

cur-next=newhead;

newhead=cur;

cur=next;

if(next)

next=next-next;

returnnewhead;

}

3、链表的中间节点

链接直达：

链表的中间节点

题目：

思路：

快慢指针

这道题要注意奇偶数，如果为奇数，如示例1，那么中间节点值就是3，反之偶数如示例2，返回第二个中间节点。此题我们定义两个指针slow和fast都指向第一个数据的位置，区别在于让slow一次走1步，fast一次走2步。当fast走到尾指针时，slow就是中间节点

代码如下：

structListNode*middleNode(structListNode*head){

structListNode*slow=head;

structListNode*fast=head;

while(fastfast-next)

slow=slow-next;

fast=fast-next-next;

returnslow;

}

4、链表中倒数第k个节点

链接直达：

链表中倒数第k个节点

题目：

思路：

快慢指针

定义两个指针slow和fast，让fast先走k步，再让slow和fast同时走，当fast走到尾部时，slow就是倒数第k个，因为这样的话slow和fast的差距始终是k个，当fast走到空时结束。此题同样可以走k-1步，不过当fast走到尾部时结束，也就是fast的下一个节点指向空时结束，都一样。先拿走k步举例，如图所示：

代码如下：

structListNode*FindKthToTail(structListNode*pListHead,intk){

//writecodehere

structListNode*fast=pListHead;

structListNode*slow=pListHead;

while(k--)

//if判断，防止k大于链表的长度

if(fast==NULL)

returnNULL;

fast=fast-next;

while(fast)

fast=fast-next;

slow=slow-next;

returnslow;

}

5、合并两个有序链表

链接直达：

合并两个有序链表

题目：

思路：

法一：归并（取小的尾插）---带头节点

假设新链表的头叫head并指向NULL，还需要定义一个指针tail来方便后续的找尾，依次比较list1和list2节点的值，把小的放到新链表head上，并更新tail，再把list1或list2更新一下。当list1和list2两个链表中一个走到空时，直接把剩下的链表所有剩下的元素拷进去即可

代码如下：

structListNode*mergeTwoLists(structListNode*list1,structListNode*list2){

//检查list1或list2一开始就为NULL的情况

if(list1==NULL)

returnlist2;

if(list2==NULL)

returnlist1;

structListNode*head=NULL;

structListNode*tail=head;

while(list1list2)

if(list1-vallist2-val)

if(tail==NULL)

head=tail=list1;

else

tail-next=list1;

tail=list1;

list1=list1-next;

else

if(tail==NULL)

head=tail=list2;

else

tail-next=list2;

tail=list2;

list2=list2-next;

//当list1和list2其中一个走到空的情况

if(list1==NULL)

tail-next=list2;

else

tail-next=list1;

returnhead;

}

法二：哨兵位的头节点

解释下带头节点：

比如说同样一个链表存1，2，3。不带头节点只有这三个节点，head指向1。而带头节点的同样存3个值，不过有4个节点，head指向头部这个节点，这个节点不存储有效数据

带头结点有如下好处，不用判断head和tail是否为空了，也不用判断list1和list2是否为空了，会方便不少。和上述思路一样，取小的下来尾插，直接链接到tail后面即可。但是要注意返回的时候要返回head的next，因为题目给的链表是不带头的，而head本身指向的就是那个头，所以要返回下一个。

代码如下：

structListNode*mergeTwoLists(structListNode*list1,structListNode*list2){

structListNode*head=NULL,*tail=NULL;

head=tail=(structListNode*)malloc(sizeof(structListNode));

head-next=NULL;

while(list1list2)

if(list1-vallist2-val)

tail-next=list1;

tail=list1;

list1=list1-next;

else

tail-next=list2;

tail=list2;

list2=list2-next;

//当list1和list2其中一个走到空的情况

if(list1==NULL)

tail-next=list2;

else

tail-next=list1;

structListNode*list=head-next;

free(head);

head=NULL

returnlist;

}

6、链表分割

链接直达：

链表分割

题目：

思路：

定义两个链表lesshead和greaterhead。遍历原链表，把x的插入到链表1，把x的插入到链表2，最后再把链表1和链表2链接起来。在定义两个尾指针以跟进链表1和2新增元素

代码如下：

classPartition{

public:

ListNode*partition(ListNode*pHead,intx){

//writecodehere

structListNode*lessHead,*lessTail,*greaterHead,*greaterTail;

lessHead=lessTail=(structListNode*)malloc(sizeof(structListNode));

greaterHead=greaterTail=(structListNode*)malloc(sizeof(structListNode));

lessTail-next=greaterTail-next=NULL;

structListNode*cur=pHead;

while(cur)

if(cur-valx)

lessTail-next=cur;

lessTail=lessTail-