1. 链表part2刷题前先把这四道题串起来看很多人刷算法题喜欢一道一道孤立地刷我自己的体会是这样刷完等于没刷过两周再看题目全都眼生。链表part2这一天的四道题——两两交换链表中的节点、删除链表的倒数第N个节点、链表相交、环形链表II其实可以当成同一类思想在不同场景下的四种变体。核心不外乎三个东西虚拟头节点、快慢指针、指针更新顺序。如果你能把四道题放在一起对比着看一次刷完收获比分散刷四五天还大。这一天的内容适合谁如果你链表基础还不牢比如对pre、cur、post三个指针的交替顺序总是一知半解建议先花半小时专门练一下「指针三连」的指向关系如果你已经能独立写出链表的增删改查那这批题正好帮你把指针操作提到「不画图也能一次写对」的程度。我刷这批题之前其实已经做过不少链表题但坦白说两两交换这种题我以前是靠硬背的直到这次系统梳理之后才真正理解每一步为什么这么写。先给一个总览。这四道题的时间复杂度都是O(n)空间复杂度都是O(1)都属于高频面试题尤其两两交换和环形链表II出现的频率非常高。环形链表II那题还涉及一个经典数学推导理解了之后你可能会觉得它其实很简单难点全在第一次相遇之后怎么办这个坎上。题目核心思路时间复杂度空间复杂度两两交换链表中的节点虚拟头节点 三指针O(n)O(1)删除链表的倒数第N个节点快慢指针 虚拟头节点O(n)O(1)链表相交长度对齐 / 双指针走过全程O(n)O(1)环形链表IIFloyd判圈 数学推导O(n)O(1)下面我按「为什么要这么做」而不是「题目答案长什么样」的思路来拆这样你下次遇到变体题比如交换相隔k个节点、删除倒数第k个节点也知道从哪里下手。2. 虚拟头节点链表题的万能起手式2.1 为什么一定要加虚拟头节点先说结论在我刷过的链表题里绝大多数涉及「删除节点」「交换节点」「在头部操作节点」的场景加一个dummy节点都不是可选项而是必选项。原因很简单——头节点没有前驱节点你能改的是它的值或者它的next但没法通过前驱来操作它这就导致头节点成了一个游离在统一逻辑之外的「特殊情况」。举个例子删除链表倒数第N个节点如果N正好等于链表长度那要删的就是头节点。如果你不设dummy就得写分支判断if (n 链长) head head.next; 否则走另一个删除逻辑。这么写不是不行但每次都要额外处理一个边界代码丑不说还容易漏。设了dummy之后头节点变成了普通节点统一用「找到目标节点的前驱然后把前驱的next指向目标节点的后继」这一套逻辑不需要任何分支判断。我见过不少初学者觉得dummy是多余的直接拿head做遍历结果写出来的代码要么在边界用例上崩要么为了处理边界写得乱七八糟。我的建议是凡是要修改链表结构的题无脑先加dummy这是成本最低的保证正确性的方式。这道题的代码复杂度提升几乎为零却能帮你把注意力从边界判断上解放出来。2.2 虚拟头节点不是万能的当然dummy也不是所有链表题都必须加。比如链表相交那题无论加不加dummy核心思路都是对齐两个链表的起始位置dummy帮不上什么忙因为那道题压根没让你修改链表结构。再比如环形链表II你只需要遍历和比较节点引用也不会改结构dummy同样没有存在感。那什么时候确定需要dummy一个很简单的判断标准你做题之前先问自己「我会不会因为修改链表结构而让头节点丢失或者需要特殊处理」。会就加。不会就别硬加。有人会把所有链表题都无脑套dummy虽然不违反什么但会让代码多出一行没意义的东西反而影响思路清晰度。我自己的习惯是凡是涉及删除、插入、反转、交换的题dummy默认加上凡是只读遍历的题默认不加想都不要想。3. 四道经典题目逐个拆解3.1 两两交换链表中的节点三指针的顺序就是生命线先看这一天的第一道硬骨头——两两交换相邻节点。题目要求给定 1-2-3-4交换得到 2-1-4-3。很多人的第一反应是改节点的值而不是改指针比如把1的值变成22的值变成1。这在部分OJ上确实能通过但面试场合千万别这么干因为交换值没有改变真实的链表结构只是「看起来」结果对了面试官一问指针关系就露馅。正确思路是先设dummy然后维护pre指针指向「待交换的两个节点」的前一个节点。每次循环里cur是第一个待交换节点post是第二个待交换节点。交换的核心就三行prev.next post # 前驱先指向后一个节点 cur.next post.next # 第一个节点指向第二个节点的后继 post.next cur # 第二个节点反过来指向第一个节点这三行执行的顺序特别讲究。很多初学者会先写 post.next cur结果发现 cur 后面那一串全丢了。原因很简单post.next 一开始还连着后面的链表你先改了它后面的节点就再也找不回来了。所以正确做法是先把 cur.next 指向 post 原来的后继把后续链表先「钉住」再动 post.next。这个顺序我建议你每次写之前都在脑子里过一遍先连后面再改前面最后指向自己。这题还有一个小坑执行完交换之后pre要移动到cur的位置。为什么不是pre pre.next.next因为pre.next已经被它指向post了pre距离交换后的第二个节点就是原来的cur正好是两步但那个位置不在pre.next.next上而是在交换后的cur上。所以老老实实写pre cur别耍小聪明。3.2 删除链表的倒数第N个节点快慢指针的经典边界删除倒数第N个节点的常规做法有两种。第一种是先遍历一遍求长度然后走 length - n 步找到目标节点的前驱把它next指向下下个节点。这种做法的缺点是遍历了两遍虽然时间复杂度还是O(n)但代码上多了一次循环不够优雅。第二种做法就是快慢指针这也是面试时比较加分的写法。快指针先走n1步然后慢指针和快指针同步往后走当快指针走到链表结尾即fast为None时慢指针恰好停在待删除节点的前一个位置。为什么是n1不是n你想想如果快指针只走n步那么同步走完后慢指针会停在待删除节点本身删它还得先找前驱等于多绕一圈。走n1步慢指针天然成为前驱直接 slow.next slow.next.next 收工。用dummy配合这个解法边界情况也变得很干净。n等于链表长度时快指针从dummy出发走n1步之后正好变成None慢指针停在dummy删除的就是原来的头节点不需要判断。我第一次写这题的时候就被这里绕晕了脑子里一直在想「快指针会不会走过头」后来干脆拿长度很短的链表仔细推了一遍才彻底清楚。建议你也这么做拿一个只有两个节点的链表手动模拟一遍快慢指针的轨迹比背十遍答案都管用。3.3 链表相交的第一种解法长度对齐链表相交这题和前面几道不太一样它不要求改结构只要求找两个链表第一次产生「同一个节点」的位置。这里的「同一个节点」指的是引用相同不是值相同。两个节点的val可能一样但内存地址不同那也不算相交。凡是拿值来判断的都是踩坑后面我会专门说。第一种解法思路很直接两个链表长度可能不一样那就先把长的那个往后挪挪到两个链表对齐为止然后两个指针同步前进第一个相等的节点就是交点。实现上先分别遍历两个链表求长度然后把较长的链表的头指针往后挪长度差那么多的步数接着两个指针一起走。这里注意求长度和找交点可以分两次遍历也可以一次遍历同时记录长度差别不大但分两次写更容易读。还有一种更简洁的写法——让两个指针分别从两个链表头出发走完自己这条就切换到对方那条由于两个指针最终走的总步数相同它们会在交点处相遇。这种写法代码量极小但理解门槛稍微高一点第一次看可能会觉得像魔法。3.4 链表相交的第二种解法双指针走完全程第二种解法代码短到让人怀疑核心就一个while循环。两个指针pA、pB分别从headA、headB出发pA走完headA之后转为走headBpB走完headB之后转为走headA。两个指针速度相同、总路程相同所以它们必然会在某一时刻走到同一点。如果两个链表相交两个指针会在交点第一次相遇如果不想交两个指针会同时走到None。为什么不相交的情况下它们的总路程分别是 lenA lenB 和 lenB lenA完全一样所以会同时遍历完两条链最后同时变成None。有人会担心死循环其实不会因为每条链都是有限的两个指针各自最多走 lenA lenB 步就会结束。这道题我觉得很有价值的地方在于它展示了「消除长度差」不只是物理上对齐长度差这一种办法你可以用「走完自己再走对方」的思路让长度差自动消除。这种思路在后面的很多双指针题里都会用到比如环形链表找入口本质上也是一种「消除差异」的思想。3.5 环形链表IIFloyd判圈法的数学推导环形链表II应该是链表part2里最需要耐心的一道题。题目要求找到环的入口节点。Floyd判圈法分两个阶段第一阶段快慢指针同时从head出发快指针每次走两步慢指针每次走一步如果链表有环两者必然在环内某个点相遇第二阶段把一个指针移回head两个指针都改为每次走一步第二次相遇的位置就是环入口。为什么成立这里有个经典的数学推导。设从head到环入口的距离是x从环入口到第一次相遇点的距离是y从相遇点绕回环入口的距离是z那么环的长度就是yz。慢指针走了xy快指针走了2(xy)。因为快指针比慢指针多走了n圈所以2(xy) xy n(yz)化简得到x (n-1)(yz) z。注意当n1时x z。也就是说从head出发走x步到达环入口从相遇点出发走z步也能到达环入口。这时候第二阶段的操作就顺理成章了慢指针重新从head出发快指针停在第一次相遇点两者都每次走一步因为它们到环入口的距离恰好相等或者说相差整数个环长所以必然在环入口相遇。这个推导我第一次看的时候来回看了三遍才真正接受。其实你不需要死记n1这个特例只要理解「两指针第一次相遇后把其中一个重置到head二者同速前进会在环入口相遇」这个结论就行。写代码时还有一个容易翻车的地方第一阶段快指针的循环条件要写 fast and fast.next因为快指针一次走两步如果链表无环它会先一步走到None不判断下一步是否存在直接访问 fast.next.next 就会报空指针。很多人在这里栽过包括我自己。4. 完整代码与实操要点4.1 标准代码实现直接抄作业把上面四道题的标准实现放在这里注释写得比较细方便你对照着写。我统一用Python如果你平时用Java或者C思路完全一样只是指针写法不同。两两交换节点class Solution: def swapPairs(self, head: Optional[ListNode]) - Optional[ListNode]: dummy ListNode(nexthead) prev dummy while prev.next and prev.next.next: cur prev.next # 待交换的第一个节点 post cur.next # 待交换的第二个节点 prev.next post # 前驱指向第二个节点 cur.next post.next # 第一个节点指向后续链表 post.next cur # 第二个节点指向第一个节点 prev cur # 前驱移动到交换后的第二个节点 return dummy.next删除倒数第N个节点class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]: dummy ListNode(nexthead) fast slow dummy for _ in range(n 1): # 快指针先走 n1 步 fast fast.next while fast: # 快慢同步走fast到None时slow停在前驱 fast fast.next slow slow.next slow.next slow.next.next return dummy.next链表相交class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - Optional[ListNode]: pa, pb headA, headB while pa ! pb: pa pa.next if pa else headB pb pb.next if pb else headA return pa环形链表IIclass Solution: def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]: slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: # 第一次相遇 slow head # 慢指针重置到head while slow ! fast: # 同速前进直到相遇 slow slow.next fast fast.next return slow return None4.2 复杂度分析与选型理由四道题的时间复杂度都是O(n)空间复杂度都是O(1)不考虑递归栈和返回节点本身。链表相交那个双指针解法很多人会纠结它到底会不会无限循环。这里给一个直观理解pA和pB各走 lenA lenB 步之后必然同时为None循环必然结束。因为当pA走完headA后会切到headBpB走完headB后会切到headA二者的总路程都是lenA lenB速度一样所以结束时机一样。至于为什么这四道题都推荐用迭代而不是递归我的理由是链表的递归写法在概念上更简洁但实际面试中迭代解法对内存更友好也更容易用画图的方式跟面试官讲清楚。尤其是两两交换递归写的版本稍不留神就把顺序搞错而迭代版本配合dummy和三指针每一步都有明确含义调试起来也直观。还有一点值得注意链表相交题目里并不存在「改结构」的需求所以不需要dummy。但是删除倒数第N个节点和两两交换都改了结构所以dummy都是必需品。你做题的时候一定要形成这种条件反射——看到「修改链表结构」就提醒自己考虑dummy看到「只读查找」就别画蛇添足。5. 踩坑实录这些错误我至少犯过一次5.1 指针更新顺序错了链表直接断掉这是两两交换里最常见的错误。有人习惯先写 post.next cur想的是「先把两者连起来」结果一执行post后面的节点全找不到了因为 post.next 原本指向链表后续被覆盖了。正确顺序是先处理后续链表的引用关系cur.next post.next再改动 post.next。我建议你把这三步当成一个固定套路记下来先连后续防止丢失再改前驱建立新的头关系最后回指完成交换。不只是两两交换链表反转、指定区间反转这些题本质都是这个套路只不过指针更多一些。5.2 快慢指针的步数差引发的问题删除倒数第N个节点的踩坑点集中在步数差上。我见过的最常见错误是让快指针走n步而不是n1步然后while fast.next作为循环条件。这么写也能过一部分用例但遇到删倒数第1个节点时会出问题慢指针会停在待删节点上你没法直接访问它的前驱。解决思路是一样的——保证慢指针最终停在目标节点的前驱位置差一步都不行。建议你自己手动推一遍边界用例链表长度恰好等于n的情况。用快慢指针加dummy的方案你会发现快指针走n1步之后正好是None慢指针停在dummy删除头节点顺利完成。这一步推完你再也不会在边界上犹豫。5.3 环形链表II的循环条件写错环形链表II第二阶段判断 while slow ! fast 没问题但第一阶段 while fast and fast.next 这个条件很多人会写成 while fast.next and fast.next.next。这两种写法在链表只有一个节点且无环的情况下前者直接退出循环返回None后者可能在访问fast.next.next之前就报错。还有一种情况是链表有两个节点时fast在第二次迭代时变成None如果循环条件里没判断fast为None就会尝试访问None.next直接抛异常。所以记住快指针每次走两步循环条件必须同时判断 fast 和 fast.next 是否为空。5.4 用值比较判断链表相交链表相交题里最让人无语的错误是拿 val 是否相等来判断「同一个节点」。两个链表可能在某个位置恰好有相同的值但节点本身根本不是同一个。正确的判定标准是引用相等也就是代码里的 pa pb而不是 pa.val pb.val。这个错误我当年也犯过原因是做数组类题目做习惯了总想着比较值。链表题里只要题目说「对象相同」「节点相同」一定要优先考虑引用比较。6. 关于链表题的一点个人总结这四道题刷完之后我最大的感觉是链表题表面上花样繁多实际就是三个套路不断排列组合。遇到修改结构的题先加dummy遇到找位置的题想快慢指针遇到指针操作永远记住先连后面再改前面。把这三个套路练成肌肉记忆链表part2这四道题基本就是送分题。就我个人经验来说链表题是最适合「手写模拟」的题型。别偷懒只看题解拿一张纸画个3到4个节点的链表把每一步指针变化都标出来比看十遍视频都管用。特别是两两交换和环形链表II画图和不画图的掌握速度差好几倍。我自己后来刷其他链表难题时也一直维持着先画图、再写代码的习惯。另外多说一句这批题在美国那边的面试里考察频率很高但不要把它当成纯粹的记忆题。真正拉开差距的不是你会不会背这四道题的标准解而是你能不能现场把为什么这样做讲清楚。面试官通常会在你写完代码之后追一个问题比如「把两两交换改成k个一组交换你打算怎么改」这时候如果你理解了指针套路顺着虚拟头和指针顺序的思路改起来并不难。最后分享一个小技巧刷完这一天的四道题后可以自己给自己出一组变式题——删除链表的倒数第k个节点进阶为删除链表的中间节点、两两交换进阶为每3个一组反转、环形链表I进阶为只判断是否有环不找入口。每组变式想清楚解法链表这一块基本就夯实了。我试过这个办法确实比单纯重复刷原题更有用。
