C 底层矩阵 · 代码永不停歇 作者主页 C 核心专栏 算法题解仓库 代码仓库一、前言前文已详解链表快慢指针、环形链表、相交链表及反转链表全家桶本文承接基础聚焦笔试面试中更高频的五大进阶题型从原理、代码到易错陷阱一次性吃透链表进阶题型二、链表删除专题删除链表的某个节点关键点在于要获得它的前驱节点否则会造成断链但这样需要单独处理头节点没有前驱节点可以引入dummy虚拟头节点解决避免单独处理题型一删除倒数第N个节点核心思路看到倒数第N个节点不难回忆起我们前一篇提到的快慢双指针算法找到倒数第N个节点但是我们需要获得其前驱节点所以需要先找到倒数第N1节点从dummy出发然后改变指针指向即可代码实现ListNode*removeNthFromEnd(ListNode*head,intN){ListNode*dummynewListNode(0);dummy-nexthead;//1.先找到倒数第N1个节点ListNode*fastdummy,*slowdummy;//快指针先移动N步for(inti0;iN;i){//若N超过了链表长度if(fastnullptr)returnhead;fastfast-next;}//2.快慢双指针同速移动while(fast-next){fastfast-next;slowslow-next;}//此时的slow就指向前驱节点//3.删除操作改变指针指向即可ListNode*prevslow,*curslow-next,*nextcur-next;prev-nextnext;deletecur;ListNode*newHeaddummy-next;deletedummy;returnnewHead;}⚠️易错点避坑指南建议引入虚拟头节点方便处理删除头节点的情况双指针同速移动时循环结束条件为fast指向尾节点而不是fast指向空在没有引入虚拟头节点时循环结束条件确实是fast指向空但如果引入了虚拟头节点相当于多增加了一个节点对应地循环结束条件也应该向左平移一位节点养成手动释放内存的习惯同时也要释放 dummy非必须但严谨实战链接Leetcode 19.删除倒数第N个节点题型二有序链表去重核心思路本质上还是删除节点的问题而且由于链表是有序的必然是一连串的删除此时涉及到两个节点值的比较所以需要用到双指针slowfast当fast遇到与slow值相同的节点就删除该节点不相同就让slow跳到fast节点继续遍历代码实现ListNode*deleteDuplicates(ListNode*head){//处理边界情况if(headnullptr||head-nextnullptr)returnhead;ListNode*slowhead,*fasthead-next;intvalslow-val;while(fast){if(fast-valval){ListNode*fnextfast-next;deletefast;fastfnext;//注意删完要连接上slow-nextfast;}else{slowfast;valslow-val;fastslow-next;}}returnhead;}实战链接LeetCode 83.删除排序链表中的重复元素题型三删除所有重复节点核心思路与上一题不同这一题只要是重复的元素都一个不留全部删除那么这里的前驱指针需要指向已确定无重复的最后一个节点遇到重复值跳过最后前驱节点的next指向跳过后的位置同样地一旦遇到前驱指针就立马想到用虚拟头节点简化边界情况的处理ListNode*deleteDuplicates(ListNode*head){if(headnullptr||head-nextnullptr)returnhead;ListNode*dummynewListNode(0);dummy-nexthead;//prev表示前驱指针指向已确定无重复的最后一个节点cur用来遍历链表ListNode*prevdummy,*curhead;while(curcur-next){if(cur-valcur-next-val){intvalcur-val;while(curcur-valval){ListNode*tmpcur;curcur-next;deletetmp;}prev-nextcur;//连接非重复段}else{prevcur;curcur-next;}}//随手释放内存ListNode*newHeaddummy-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*cur1list1,*cur2list2;ListNode*dummynewListNode(0);ListNode*taildummy;//只要有一个链表不为空就要继续while(cur1||cur2){//为空取INT_MAX不影响比较逻辑intval1cur1nullptr?INT_MAX:cur1-val;intval2cur2nullptr?INT_MAX:cur2-val;if(val1val2){tail-nextcur1;tailcur1;cur1cur1-next;}else{tail-nextcur2;tailcur2;cur2cur2-next;}}ListNode*newHeaddummy-next;deletedummy;returnnewHead;}递归版核心思想将链表分成一个个节点直到节点为空为止通过比较每个节点的大小选择较小的节点作为头节点ListNode*mergeTwoLists(ListNode*list1,ListNode*list2){// 递归终止条件其中一个链表为空返回另一个if(list1nullptr)returnlist2;if(list2nullptr)returnlist1;// 选择较小值的节点递归合并后续链表if(list1-vallist2-val){list1-nextmergeTwoLists(list1-next,list2);returnlist1;}else{list2-nextmergeTwoLists(list1,list2-next);returnlist2;}}实战连接LeetCode 21.合并两个有序链表四、回文链表核心思路用快慢指针找到链表中点慢指针走1步快指针走2步快指针到达尾时慢指针指向中点反转链表后半段双指针分别从链表头和反转后的后半段头开始逐一比对值全部相等则为回文否则不是boolisPalindrome(ListNode*head){if(headnullptr||head-nextnullptr)returnhead;ListNode*slowhead,*fasthead;//1.快慢指针找中点while(fastfast-next){slowslow-next;fastfast-next-next;}//2.将后一段链表翻转ListNode*prenullptr,*curslow;while(cur){ListNode*nextcur-next;cur-nextpre;precur;curnext;}//3.依次比较即可ListNode*tmphhead;while(pre){if(tmph-val!pre-val)returnfalse;tmphtmph-next;prepre-next;}returntrue;}⚠️易错点避坑指南如果链表长度为奇数的话后半段长度比前半段长度少一但不影响结果因为翻转的时候是以较短的链表作为循环条件注意快慢指针和翻转时的循环条件实战连接LeetCode 234.回文链表五、奇偶链表核心思路两个指针分别指向奇偶链表的头然后遍历原链表分别接在奇偶链表的后面即可最后将偶数链表接在奇数链表后面ListNode*oddEvenList(ListNode*head){//边界情况处理n 0、1、2if(headnullptr||head-nextnullptr||head-next-nextnullptr)returnhead;ListNode*oddhead;// 奇数链头与尾ListNode*evenhead-next;// 偶数链头与尾ListNode*evenHeadeven;// 保存偶数链头// 当偶数节点和偶数节点的下一个节点都存在时才能继续while(eveneven-next){odd-nexteven-next;oddodd-next;even-nextodd-next;eveneven-next;}// 奇数链的尾部连接偶数链的头部odd-nextevenHead;returnhead;}⚠️易错点避坑指南必须提前保存 evenHead因为 even 指针在遍历中会移动循环条件为 even even-next 确保偶数链至少有两个节点时才能继续交错链接否则结束实战连接LeetCode 328.奇偶链表六、链表归并排序先回顾一下归并排序的要点分将链表划分成两段大致相同长度的链表治递归地对两个子序列进行排序合将两个已排序的两个子序列进行合并排序核心原理1.找到中点利用快慢指针将链表分成两段注意要将链表断开2.递归处理两段3.将两段连接起来classSolution{//分为了三个模块排序模块找中点模块合并有序链表模块public://排序模块ListNode*sortList(ListNode*head){if(headnullptr||head-nextnullptr)returnhead;// 1. 找中点并断开为两个链表ListNode*midfindMiddle(head);ListNode*rightHeadmid-next;mid-nextnullptr;// 2. 递归排序左右两部分ListNode*leftsortList(head);ListNode*rightsortList(rightHead);// 3. 合并两个有序链表returnmerge(left,right);}private://找中点模块ListNode*findMiddle(ListNode*head){ListNode*slowhead;ListNode*fasthead-next;// 关键点fast 从 head-next 开始while(fastfast-next){slowslow-next;fastfast-next-next;}returnslow;}//合并有序链表模块ListNode*merge(ListNode*list1,ListNode*list2){ListNode*cur1list1,*cur2list2;ListNode*dummynewListNode(0);ListNode*taildummy;//只要有一个链表不为空就要继续while(cur1||cur2){intval1cur1nullptr?INT_MAX:cur1-val;intval2cur2nullptr?INT_MAX:cur2-val;if(val1val2){tail-nextcur1;tailcur1;cur1cur1-next;}else{tail-nextcur2;tailcur2;cur2cur2-next;}}ListNode*newHeaddummy-next;deletedummy;returnnewHead;}};⚠️易错点避坑指南注意在设置快慢双指针的时候fast head-next是因为如果 fast 从 head 开始那么对于长度为 2 的链表慢指针会走到第二个节点导致切分后左半边有两个节点右半边为空这样递归会死循环注意找完中点后要将两个链表断开否则没办法进行排序建议像我这样分模块写不同的函数这样思路更加清晰出错更易调试实战链接LeetCode 148.排序链表七、总结本文整合链表进阶五大核心题型覆盖删除、合并、回文、奇偶拆分、排序所有题型均复用前文已学技巧双指针、反转链表形成完整的链表解题思维体系吃透本文可轻松应对笔试面试中90%以上的链表进阶考题后续将补充链表压轴难题合并K个有序链表、复制带随机指针的链表持续完善【底层技术矩阵】算法进阶之路的链表板块请大家敬请期待~