💜 C++ 底层矩阵 · 代码永不停歇| 👤 作者主页 | 🔥 C++ 核心专栏 |
|---|---|
| 💾 算法题解仓库 | 📁 代码仓库 |
一、前言
前文已详解链表快慢指针、环形链表、相交链表及反转链表全家桶，本文承接基础，聚焦笔试面试中更高频的五大进阶题型，从原理、代码到易错陷阱，一次性吃透链表进阶题型
二、链表删除专题
删除链表的某个节点关键点在于要获得它的前驱节点，否则会造成断链，但这样需要单独处理头节点（没有前驱节点），可以引入dummy虚拟头节点解决，避免单独处理
题型一：删除倒数第N个节点
🤔核心思路
看到倒数第N个节点，不难回忆起我们前一篇提到的
快慢双指针算法找到倒数第N个节点，但是我们需要获得其前驱节点，所以需要先找到倒数第N+1节点（从dummy）出发，然后改变指针指向即可
代码实现：
ListNode*removeNthFromEnd(ListNode*head,intN){ListNode*dummy=newListNode(0);dummy->next=head;//1.先找到倒数第N+1个节点ListNode*fast=dummy,*slow=dummy;//快指针先移动N步for(inti=0;i<N;i++){//若N超过了链表长度if(fast==nullptr)returnhead;fast=fast->next;}//2.快慢双指针同速移动while(fast->next){fast=fast->next;slow=slow->next;}//此时的slow就指向前驱节点//3.删除操作（改变指针指向即可）ListNode*prev=slow,*cur=slow->next,*next=cur->next;prev->next=next;deletecur;ListNode*newHead=dummy->next;deletedummy;returnnewHead;}⚠️易错点避坑指南
- 建议引入虚拟头节点，方便处理删除头节点的情况
- 双指针同速移动时循环结束条件为
fast指向尾节点，而不是fast指向空，在没有引入虚拟头节点时循环结束条件确实是fast指向空，但如果引入了虚拟头节点，相当于多增加了一个节点，对应地，循环结束条件也应该向左平移一位节点 - 养成手动释放内存的习惯，同时也要释放 dummy（非必须但严谨）
实战链接：Leetcode 19.删除倒数第N个节点
题型二：有序链表去重
🤔核心思路
本质上还是删除节点的问题，而且由于链表是有序的，必然是一连串的删除，此时涉及到两个节点值的比较，所以需要用到双指针，slow，fast，当fast遇到与slow值相同的节点就删除该节点，不相同，就让slow跳到fast节点继续遍历
代码实现
ListNode*deleteDuplicates(ListNode*head){//处理边界情况if(head==nullptr||head->next==nullptr)returnhead;ListNode*slow=head,*fast=head->next;intval=slow->val;while(fast){if(fast->val==val){ListNode*fnext=fast->next;deletefast;fast=fnext;//注意删完要连接上slow->next=fast;}else{slow=fast;val=slow->val;fast=slow->next;}}returnhead;}实战链接：LeetCode 83.删除排序链表中的重复元素
题型三：删除所有重复节点
🤔核心思路
与上一题不同，这一题只要是重复的元素都一个不留，全部删除，那么这里的前驱指针需要指向已确定无重复的最后一个节点，遇到重复值跳过，最后前驱节点的next指向跳过后的位置，同样地，一旦遇到前驱指针，就立马想到用虚拟头节点简化边界情况的处理
ListNode*deleteDuplicates(ListNode*head){if(head==nullptr||head->next==nullptr)returnhead;ListNode*dummy=newListNode(0);dummy->next=head;//prev表示前驱指针：指向已确定无重复的最后一个节点，cur用来遍历链表ListNode*prev=dummy,*cur=head;while(cur&&cur->next){if(cur->val==cur->next->val){intval=cur->val;while(cur&&cur->val==val){ListNode*tmp=cur;cur=cur->next;deletetmp;}prev->next=cur;//连接非重复段}else{prev=cur;cur=cur->next;}}//随手释放内存ListNode*newHead=dummy->next;deletedummy;returnnewHead;}⚠️易错点避坑指南
- 外层循环条件为cur和cur->next不为空，这样才能保证不造成空指针解引用
- 注意在删完重复段的时候，要将前驱节点与非重复节点连接起来，避免断链
✅删除专题总结
删除类核心技巧：
可以引入虚拟头节点解决头节点删除问题
双指针定位目标节点，删除后及时释放内存
有序去重利用「相邻重复」特性，找到前驱指针是关键
删除节点后，工程实践中建议手动释放内存，避免内存泄漏；但 LeetCode 判题不强制要求释放，可按需处理
删除所有重复节点时，循环条件必须是 cur && cur->next，否则当 cur 为 nullptr 时访问 cur->next 会崩溃
三、合并两个有序链表
- 迭代版
🤔核心思想：
类似归并排序中的合并过程：每次取两个链表头中较小的节点接入结果链，为了避免一个链表遍历完后，还要单独处理另一个链表，我们只用一个循环搞定：只要有链表不为空就继续，就算有链表为空，只要保证比较大小时不影响结果即可（取INT_MAX）
时间复杂度为O(n)
代码实现
ListNode*mergeTwoLists(ListNode*list1,ListNode*list2){ListNode*cur1=list1,*cur2=list2;ListNode*dummy=newListNode(0);ListNode*tail=dummy;//只要有一个链表不为空就要继续while(cur1||cur2){//为空取INT_MAX不影响比较逻辑intval1=cur1==nullptr?INT_MAX:cur1->val;intval2=cur2==nullptr?INT_MAX:cur2->val;if(val1<val2){tail->next=cur1;tail=cur1;cur1=cur1->next;}else{tail->next=cur2;tail=cur2;cur2=cur2->next;}}ListNode*newHead=dummy->next;deletedummy;returnnewHead;}- 递归版
🤔核心思想：
将链表分成一个个节点直到节点为空为止，通过比较每个节点的大小选择较小的节点作为头节点
ListNode*mergeTwoLists(ListNode*list1,ListNode*list2){// 递归终止条件：其中一个链表为空，返回另一个if(list1==nullptr)returnlist2;if(list2==nullptr)returnlist1;// 选择较小值的节点，递归合并后续链表if(list1->val<=list2->val){list1->next=mergeTwoLists(list1->next,list2);returnlist1;}else{list2->next=mergeTwoLists(list1,list2->next);returnlist2;}}实战连接：LeetCode 21.合并两个有序链表
四、回文链表
🤔核心思路
- 用
快慢指针找到链表中点（慢指针走1步，快指针走2步，快指针到达尾时，慢指针指向中点）- 反转链表后半段
- 双指针分别从链表头和反转后的后半段头开始，
逐一比对值，全部相等则为回文，否则不是
boolisPalindrome(ListNode*head){if(head==nullptr||head->next==nullptr)returnhead;ListNode*slow=head,*fast=head;//1.快慢指针找中点while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}//2.将后一段链表翻转ListNode*pre=nullptr,*cur=slow;while(cur){ListNode*next=cur->next;cur->next=pre;pre=cur;cur=next;}//3.依次比较即可ListNode*tmph=head;while(pre){if(tmph->val!=pre->val)returnfalse;tmph=tmph->next;pre=pre->next;}returntrue;}⚠️易错点避坑指南
- 如果链表长度为奇数的话，后半段长度比前半段长度少一，但不影响结果，因为翻转的时候是以较短的链表作为循环条件
- 注意快慢指针和翻转时的循环条件
实战连接：LeetCode 234.回文链表
五、奇偶链表
🤔核心思路
两个指针分别指向奇偶链表的头，然后遍历原链表，分别接在奇偶链表的后面即可，最后将偶数链表接在奇数链表后面
ListNode*oddEvenList(ListNode*head){//边界情况：处理n = 0、1、2if(head==nullptr||head->next==nullptr||head->next->next==nullptr)returnhead;ListNode*odd=head;// 奇数链头与尾ListNode*even=head->next;// 偶数链头与尾ListNode*evenHead=even;// 保存偶数链头// 当偶数节点和偶数节点的下一个节点都存在时才能继续while(even&&even->next){odd->next=even->next;odd=odd->next;even->next=odd->next;even=even->next;}// 奇数链的尾部连接偶数链的头部odd->next=evenHead;returnhead;}⚠️易错点避坑指南
- 必须提前保存 evenHead，因为 even 指针在遍历中会移动
- 循环条件为 even && even->next 确保偶数链至少有两个节点时才能继续交错链接，否则结束
实战连接：LeetCode 328.奇偶链表
六、链表归并排序
😊先回顾一下归并排序的要点
- 分：将链表划分成两段大致相同长度的链表
- 治：递归地对两个子序列进行排序
- 合：将两个已排序的两个子序列进行合并排序
🤔核心原理
1.找到中点（利用快慢指针），将链表分成两段，注意要将链表断开
2.递归处理两段
3.将两段连接起来
classSolution{//分为了三个模块：排序模块，找中点模块，合并有序链表模块public://排序模块ListNode*sortList(ListNode*head){if(head==nullptr||head->next==nullptr)returnhead;// 1. 找中点并断开为两个链表ListNode*mid=findMiddle(head);ListNode*rightHead=mid->next;mid->next=nullptr;// 2. 递归排序左右两部分ListNode*left=sortList(head);ListNode*right=sortList(rightHead);// 3. 合并两个有序链表returnmerge(left,right);}private://找中点模块ListNode*findMiddle(ListNode*head){ListNode*slow=head;ListNode*fast=head->next;// 关键点：fast 从 head->next 开始while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}returnslow;}//合并有序链表模块ListNode*merge(ListNode*list1,ListNode*list2){ListNode*cur1=list1,*cur2=list2;ListNode*dummy=newListNode(0);ListNode*tail=dummy;//只要有一个链表不为空就要继续while(cur1||cur2){intval1=cur1==nullptr?INT_MAX:cur1->val;intval2=cur2==nullptr?INT_MAX:cur2->val;if(val1<val2){tail->next=cur1;tail=cur1;cur1=cur1->next;}else{tail->next=cur2;tail=cur2;cur2=cur2->next;}}ListNode*newHead=dummy->next;deletedummy;returnnewHead;}};⚠️易错点避坑指南
- 注意在设置快慢双指针的时候，fast = head->next，是因为如果 fast 从 head 开始，那么对于长度为 2 的链表，慢指针会走到第二个节点，导致切分后左半边有两个节点，右半边为空，这样递归会死循环
- 注意找完中点后要将两个链表断开，否则没办法进行排序
- 建议像我这样分模块写不同的函数，这样思路更加清晰，出错更易调试
实战链接：LeetCode 148.排序链表
七、总结
本文整合链表进阶五大核心题型，覆盖删除、合并、回文、奇偶拆分、排序，所有题型均复用前文已学技巧（双指针、反转链表），形成完整的链表解题思维体系，吃透本文，可轻松应对笔试面试中90%以上的链表进阶考题
后续将补充链表压轴难题（合并K个有序链表、复制带随机指针的链表），持续完善【底层技术矩阵】算法进阶之路的链表板块，请大家敬请期待~
