🔥博客主页：小王又困了
📚系列专栏：数据结构
🌟人之为学，不日近则日退
❤️感谢大家点赞👍收藏⭐评论✍️
目录
🗒️前言：
在上一期中我们给大家介绍了单链表，也了解了单链表的实现。接下来就让我们进入实践，练习一些经典题目，让我们对单链表的理解更加深入。
一、移除链表元素
题目：
💡方法一：
我们使用两个指针遍历数组，遇到与 val 相同的数据域，就删除这个节点。我们在思考问题时要想全面，当要删除头节点时，常规方法就无法实现，对于删除头节点要做单独处理。
🍩常规删除：
🍩头节点删除
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* prev=NULL; struct ListNode* cur=head; while(cur!=NULL) { //删除 if(val==cur->val) { //头删 if(cur==head) { head=cur->next; free(cur); cur=head; } //常规 else { prev->next=cur->next; free(cur); cur=prev->next; } } //遍历 else { prev=cur; cur=cur->next; } } return head; }
💡方法二：
我们通过遍历，把节点的数据域不等于val的节点尾接到新的链表中。我们要考虑第一个节点是不是要删除的。最后一个节点的指针域置空要放在循环结束后，判断tail是否为空指针。
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* newhead=NULL; struct ListNode* tail=NULL; struct ListNode* cur=head; while(cur) { if(cur->next==val) { //删除 struct ListNode* del=cur; cur=cur->next; free(del); } else { //尾插 if(tail==NULL) { newhead=tail=cur; //tail=cur; } else { tail->next=cur; tail=tail->next; } cur=cur->next; } } if(tail) { tail->next=NULL; } return newhead; }
二、链表的中间节点
题目：
💡方法一：
我们可以定义两个指针，快指针一次走两步，慢指针一次走一步，当快指针走到结尾时，慢指针正好走了一半，这样我们就可以找到中间节点。
struct ListNode* middleNode(struct ListNode* head) { struct ListNode* fast=head; struct ListNode* slow=head; while(fast&&fast->next) { fast=fast->next->next; slow=slow->next; } return slow; }
三、链表中倒数第k个结点
题目：
💡方法一：
我们可以参考上一题的方法，同样定义快慢指针，想让快指针走k步，然后在同时走，走到fast为空指针就找了倒数第k个节点。有可能链表没有k个节点，所以我们要加入判断。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode* fast=pListHead; struct ListNode* slow=pListHead; while(k--) { //链表没有k步长 if(fast==NULL) { return NULL; } fast=fast->next; } while(fast!=NULL) { fast=fast->next; slow=slow->next; } return slow; }
四、反转链表
题目：
💡方法一：
我们定义三个指针n1,n2,n3，来改变节点链接的顺序。将头节点变为尾节点，当n2为空指针时，n1就为链表的头节点，只需返回n1就可以。两个指针倒方向，一个指针保持下一个。
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* n1=NULL; struct ListNode* n2=head; struct ListNode* n3; if(n2) { n3=n2->next; } while(n2) { n2->next=n1; //往后走 n1=n2; n2=n3; if(n3) { n3=n3->next; } } return n1; }
💡方法二：
将链表的节点一个一个拿下来，进行头插。这里要注意赋值的顺序。
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur=head; struct ListNode* newnode=NULL; while(cur) { //保存节点 struct ListNode* next=cur->next; //头插 cur->next=newnode; newnode=cur; cur=next; } return newnode; }
五、合并两个有序链表
题目：
💡方法一：
我们创建一个带哨兵位的链表，这样在尾插时就不用判断是否是第一个节点，可以提高效率。要记住在最后要将哨兵位的空间释放。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } struct ListNode* head=NULL; struct ListNode* tail=NULL; //创建一个哨兵位 head=tail=(struct ListNode*)malloc(sizeof(struct ListNode)); while(list1&&list2) { if(list1->val<list2->val) { tail->next=list1; tail=tail->next; list1=list1->next; } else { tail->next=list2; tail=tail->next; list2=list2->next; } } if(list1) { tail->next=list1; } if(list2) { tail->next=list2; } struct ListNode* del=head; head=head->next; free(del); return head; }
本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。你们的支持就是博主最大的动力。