算法训练营第四天链表专题正式上线。今天的任务很明确24. 两两交换链表中的节点、19. 删除链表的倒数第N个节点、面试题 02.07. 链表相交、142. 环形链表II。没做之前觉得链表题不就是指针指来指去嘛真正上手写才发现next指针一旦改乱就跟拆了毛线团一样越扯越紧。这篇不聊废话直接讲这几道题怎么想、怎么写以及哪些地方必须画图才能不翻车。适合刚学链表想系统过一遍的初学者也适合刷过一遍但总在指针顺序上犯迷糊的同学。1. 为什么链表题离不开虚拟头节点从24题的next指针地狱说起1.1 这道题的核心考点不是交换而是重连时的“保后路”24题要求两两交换相邻节点比如 1-2-3-4 变成 2-1-4-3。很多人第一反应是交换值不就行了把1和2的val换一下3和4的val换一下。但题目明确要求“交换节点”不是交换值。如果只换val节点之间的指针关系没变遇到需要操作指针的场景就完全失效。训练营里反复强调这一点——链表题练的是指针操作不是值操作。真正难的地方在于交换两个节点最少牵动三组指针。以 1-2-3 为例要把1和2交换需要让前驱节点指向2、2指向1、1指向3。这里最容易被忽视的是“前驱节点”。头节点没有前驱所以很多人在处理前两个节点时要单独写逻辑写着写着就漏了。1.2 为什么我用虚拟头节点而不是单独处理头节点虚拟头节点dummy node的思路很简单在真正的头节点前面加一个不参与业务逻辑的哨兵节点让它的 next 指向 head。这样原本“头节点没有前驱”的问题就消失了所有节点都统一处理。我第一次做这道题时偷懒没加虚拟头节点结果是交换前两个节点写一份代码交换后续节点又写一份代码两段逻辑还不太一样改起来特别容易乱。后来加了 dummy代码逻辑完全统一循环里只需要关心当前要交换的两个节点和它们的前驱不需要判断“我是不是在处理头节点”。这类题型只要涉及头节点可能被改变我都会先加 dummy省掉一整类边界问题。1.3 24题的完整解法四指针协作先连后断class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def swapPairs(head: ListNode) - ListNode: dummy ListNode(0, head) pre dummy while pre.next and pre.next.next: cur pre.next nex cur.next # 核心三连先把两个节点摘出来重连 cur.next nex.next nex.next cur pre.next nex # 移动 pre 到下一对的前驱位置 pre cur return dummy.next这个解法里最关键的是那三行重连操作顺序必须严格cur.next nex.next让第一个节点指向第二个节点的下一个节点也就是后一对的第一个节点nex.next cur让第二个节点回头指向第一个节点pre.next nex让前驱节点指向交换后的第一个节点即原来的第二个节点如果把pre.next nex放到最前面pre 的 next 就变了cur 还能通过原来的引用找到但代码的可读性会差很多。我的习惯是“先处理中间的连接再处理前驱的连接”这样每一步都只动必要的指针逻辑清楚。1.4 交换逻辑里的两个高频bug第一个bug是循环条件写错。这里要交换的是pre.next和pre.next.next所以循环条件必须同时判断这两个都不为空。写成while cur and cur.next也没错但pre移动之后cur未必是pre.next容易看晕。建议直接用while pre.next and pre.next.next跟操作对象完全对应。第二个bug是交换完之后 pre 的移动位置。很多人写成pre pre.next但交换完之后pre.next指向的是已经换到前面的节点原来的第二个节点正确的pre位置应该是交换后的第二个节点即原来的第一个节点cur。写成pre cur才对因为cur现在已经在后面了是下一对节点的前驱。这道题还有一个易错点是链表长度为奇数的情况比如 1-2-3交换后应该是 2-1-3最后那个3不用动。while pre.next and pre.next.next这个条件天然处理了这种情况pre走到最后时会发现只剩下一个节点循环直接退出。2. 删除倒数第N个节点双指针一次遍历的核心在于保持固定距离2.1 为什么先想“两次遍历”再想双指针19题是删除倒数第N个节点比如 1-2-3-4-5删除倒数第2个得到 1-2-3-5。最朴素的想法是先遍历一遍求链表长度len再从头走到len - N的位置把 target 节点删掉。这个方法完全正确时间复杂度 O(len)但需要两次遍历。双指针法只用一次遍历让一个指针先走N步然后两个指针一起走当快指针走到链表末尾时慢指针恰好停在待删节点的前一个位置。这个“恰好”不是巧合是因为快指针和慢指针之间始终保持N步的距离快指针到终点时慢指针距离终点也正好是N步也就是倒数第N个节点的前驱。2.2 快慢指针的初始化细节fast先走N步还是N1步这里有一个非常经典的细节要删除倒数第N个节点正确的做法是让快指针先走N步然后快慢一起走快指针到达 null 时停止此时慢指针指向待删节点的前驱。为什么不是先走N1步如果你想让慢指针直接指向待删节点那可以让快指针先走N1步。但删除节点需要前驱所以让慢指针停在前驱位置更自然。我倾向于用“先走N步 慢指针从前驱出发”的方案因为这样慢指针不需要额外回退一步代码和思维都简单。另一个细节是快慢指针初始时都指向虚拟头节点 dummy而不是 head。如果不加 dummy当删除的是头节点时慢指针需要前驱但它没有前驱又要单独写判断。加了 dummy删除头节点的场景和其他节点完全一致。2.3 代码实现与边界删除头节点为什么会翻车def removeNthFromEnd(head: ListNode, n: int) - ListNode: dummy ListNode(0, head) fast dummy slow dummy # 快指针先走 n 步 for _ in range(n): fast fast.next # 快慢一起走直到 fast 到达链表末尾 while fast.next: fast fast.next slow slow.next # slow 现在指向待删节点的前驱 slow.next slow.next.next return dummy.next这里我用while fast.next而不是while fast是因为我要让 slow 停在待删节点的前驱而不是待删节点本身。当 fast 指向最后一个节点时fast.next为 null循环停止此时 slow 恰好指向倒数第N1个节点。不删头的场景好理解删头的场景就考验 dummy 的作用了。假设链表是 1-2n2删除倒数第2个就是删除头节点1。fast 先走2步指向尾部节点2开始循环fast.next为null循环不执行slow 还停在 dummyslow.next.next正好是2删除成功。如果没有 dummyslow 初始指向 head那么 slow 指向1slow.next.next是 null 的下一个直接报错。2.4 对“倒数第N个”题型的通用处理模板做完这道题我总结了一个通用模板凡是要操作链表倒数第K个节点都可以用 dummy 双指针。快指针先走K步然后快慢同步移动快指针到达末尾时慢指针指向目标前驱。这个模板可以用在很多地方比如找到倒数第K个节点的值、删除倒数第K个节点、交换倒数第K个节点和正数第K个节点。用这个模板时注意一点n 的合法性判断。实际笔试中 n 一定合法但如果你在写工具代码最好先判断 n 是否小于等于链表长度。快指针走 n 步时如果提前遇到 null说明 n 不合法直接返回原链表比较稳妥。3. 链表相交先把两条链的长度差拉平交点自然浮出水面3.1 题目到底在问什么为什么判断的是指针不是值面试题02.07要求判断两条链表是否相交并返回交点。很多人一开始会误以为要比较节点的值实际上链表相交指的是两个链表从某个节点开始后面所有的节点都完全相同因为每个节点只有一个next一旦next相同后续必然全同。所以判断相交本质是判断a b这种指针引用相等而不是a.val b.val。值相等的节点可以有很多但指向同一个节点的指针只有一份。判断指针相等才是题目要求的。我看过不少人在评论区问“为什么不能用值比较”因为两个完全不相交的链表值完全可能在某一段相同比如两条链都含有值为3的节点但它们是两个不同的节点对象。3.2 长度差法先走差值步再齐头并进两条链表相交从交点开始往后完全重合所以交点一定在两条链的“后半段”某个位置。如果它们的长度不一样那么较长的链前面多出来的一部分在交点之前必然不可能有交点因为较短链根本没有这一部分。所以先把长链的指针向前移动长度差值步让两个指针离各自链表末尾的距离相同然后再一起走边走边比较指针是否相等。def getIntersectionNode(headA: ListNode, headB: ListNode) - ListNode: if not headA or not headB: return None # 计算两个链表的长度 lenA, lenB 0, 0 pA, pB headA, headB while pA: lenA 1 pA pA.next while pB: lenB 1 pB pB.next # 让长链先走差值步 pA, pB headA, headB if lenA lenB: for _ in range(lenA - lenB): pA pA.next else: for _ in range(lenB - lenA): pB pB.next # 两个指针同时移动寻找交点 while pA and pB: if pA pB: return pA pA pA.next pB pB.next return None这个解法的时间复杂度是 O(lenA lenB)空间复杂度 O(1)是面试里比较标准的答案。先统计长度这步看起来繁琐但换来的是完全不用额外空间的干净逻辑。3.3 齐头并进时的快速退出技巧两个指针一起走的时候判断条件是while pA and pB。为什么不是while pA ! pB因为如果两条链不相交两个指针会同时走到 null此时pA ! pB永远成立null不等于null吗在Python里None None是成立的所以用while pA ! pB也能退出。但从可读性上讲while pA and pB更直观只要两个指针都还没走到尽头就继续找一旦有一个先到null说明没有交点。这样即使不写哨兵节点也不会走入死循环。3.4 另一种双指针写法交换遍历法除了长度差法还有一种更简练的写法值得知道让pA走到末尾后跳到headB继续走让pB走到末尾后跳到headA继续走。这样两个指针走过的总长度相同如果有交点它们必然在交点处相遇如果没有交点它们会同时走到null。def getIntersectionNode(headA: ListNode, headB: ListNode) - ListNode: pA, pB headA, headB while pA ! pB: pA pA.next if pA else headB pB pB.next if pB else headA return pA这种写法更短但理解门槛稍高。它的核心原理是pA 走完 lenA 再走 lenBpB 走完 lenB 再走 lenA二者最终走的总步数相同。如果两个链表相交最后一段重叠部分会让二者在某一步重合如果不相交二者最终同时走到null。我建议先掌握长度差法再学交换遍历法二者原理相通只是表达方式不同。4. 环形链表II相遇点不是终点入口要靠数学推导确定4.1 快慢指针只能判断“有没有环”找不到入口142题有两个要求判断链表是否有环如果有找出环的入口节点。判断有没有环很简单用快慢指针快指针每次走两步慢指针每次走一步。如果有环快指针最终一定会追上慢指针相当于在环形跑道上速度快的人迟早套圈追上速度慢的人。但相遇点不是入口。很多人做到这一步就停了直接把相遇点返回这是错的。快慢指针的相遇点取决于环的大小和链表进入环之前那段“尾巴”的长度不同结构会给出完全不同的相遇位置。要找到入口需要再走一个数学推导步骤。4.2 入口位置的数学推导x、y、z三个距离之间的关系假设链表头到环入口的距离为 x入口沿链表方向到快慢指针相遇点的距离为 y相遇点继续沿链表方向回到入口的距离为 z那么环的长度 L y z。慢指针从出发到相遇一共走了 x y 步。快指针走了两倍的慢指针距离即 2(x y)。同时快指针在环内一定比慢指针多走了若干圈。设快指针在环内比慢指针多走了 k 圈于是有2(x y) x y kL x y kL x kL - y当 k1 时x L - y z。也就是说从链表头走 x 步到入口和从相遇点走 z 步回到入口距离是一样的。所以做法是让一个指针从链表头出发另一个指针从相遇点出发两者都一次走一步它们一定会在入口处相遇。当 k 1 时x kL - y (k-1)L z也就是说从相遇点出发的指针先绕几圈再走 z 步到入口仍然和从头出发的指针在入口相遇。所以“头指针和相遇点指针同步走”这个结论对所有情况都成立不需要额外判断k的值。4.3 代码实现三个容易踩的坑def detectCycle(head: ListNode) - ListNode: if not head or not head.next: return None slow head fast head # 第一步找到相遇点 while fast and fast.next: slow slow.next fast fast.next.next if slow fast: break # 如果没有环 if not fast or not fast.next: return None # 第二步从头和相遇点同步走再次相遇就是入口 ptr1 head ptr2 slow while ptr1 ! ptr2: ptr1 ptr1.next ptr2 ptr2.next return ptr1第三个坑是while fast and fast.next里的循环顺序。因为 fast 每次走两步如果不判断fast.next是否为null第二步就会访问fast.next.next此时如果fast.next为null直接报错。我曾经把条件写成while fast.next and fast.next.next漏掉了fast本身为null的情况在空链表上运行直接崩溃。最好先用if not head or not head.next挡掉空链表和单节点链表再进入循环。还有一个容易忽略的点找到相遇点后必须用另一个指针从 head 出发而不是让 slow 回到 head。因为 slow 已经在相遇点上了它的位置不能变我们要找的是“head到入口的距离”和“相遇点到入口的距离”相同需要两个指针从两个不同的起点同时走。4.4 为什么有人会卡在while条件的死循环上我在讨论区见过一个很典型的错误第二步的循环写成while True然后在里面判断ptr1 ptr2就返回结果在无环链表上报错或者死循环。无环时第一步就已经返回 None 了能走到第二步说明一定有环所以while ptr1 ! ptr2这个条件理论上必然会在某次循环中退出——因为两个指针最终一定会在入口相遇。但要注意这个“必然相遇”依赖一个前提两个指针每次各走一步而不是一个走两步一个走一步。如果有人把第一步的快慢节奏用到第二步让一个指针走两步一个走一步那么它们不一定会同时到达入口可能一个已经绕到前面去了另一个还在后面导致永远等不到相等。我测试过这个错误写法在特定环结构下确实会陷入死循环。记住第二步一定要两个指针都保持一次走一步。5. 四道题串练之后我总结的链表三板斧与调试方法5.1 三板斧画图、备份指针、先连后断做完这四道题我最大的感受是链表操作本质上是一场指针连线游戏只要愿意画图题目难度直接砍半。每次动手写代码之前我至少画6个节点的示意图把两个节点、前驱、后继都标出来然后模拟一遍指针变化再开始写代码。看起来费时间实际上比边写边想快得多。第二招是备份指针。凡是准备修改某个节点的 next 指向先把原来的 next 保存到临时变量比如24题里的nex cur.next。很多bug不是逻辑想错了而是某个中间值没有保存被覆盖后找不回来。写代码时多写一行备份换来的是后续调试时间的大幅减少。第三招是先连后断。调整节点关系时先把新连接建立起来再断开旧连接。比如交换两个相邻节点先让第二个节点指向第一个节点再让第一个节点指向后一组的第一个节点最后才让前驱指向第二个节点。这样即使中间某一步写错了链表仍然是一条完整可访问的链不会出现间断。5.2 边界条件清单每次做题前先过一遍场景是否需要dummy循环条件参考最容易踩的坑空链表可不加先判None访问None.next直接异常单节点链表视操作而定先判head.next交换/删除后节点丢失操作头节点建议加统一逻辑pre.next指错链表长度为奇数正常处理保留末节点误删最后一个节点快慢指针中快指针步长为2-fast and fast.nextfast.next.next访问空指针这张表我从第四天开始一直贴在笔记里后续做链表题反复用。遇到新题型先对着表过一遍能少犯一半错误。5.3 本地调试链表的实用技巧刷题网站上的报错信息有时候不够直观尤其是指针类的错误最容易出现的情况是“明明逻辑看起来对了但提交后超时或者返回错误链表”。强烈建议在本地IDE里写一个打印链表的辅助函数把每一步的结果打出来def printList(head): res [] cur head while cur: res.append(str(cur.val)) cur cur.next print( - .join(res))我调试24题时就是在每个交换步骤后调用printList(dummy.next)可以直观看到每轮循环结束后链表的状态。还有一个技巧是在关键位置打印指针引用的 id比如print(id(pre), id(cur), id(nex))能确认每个变量到底指向哪个节点避免把“值相同”误判成“指针相同”。对于环形链表II这题本地调试要小心如果代码死循环打印链表会停不下来。我的办法是在打印函数里加一个计数器超过一定次数自动返回。5.4 错误提示背后的常见原因提交时如果遇到“Time Limit Exceeded”大概率是链表被改出了环或者指针没有及时后移导致死循环。遇到“AttributeError: NoneType object has no attribute next”说明某个节点为null时还被访问了 next回到边界条件里检查有没有处理空链表和单节点。遇到结果与预期不符优先检查指针赋值顺序尤其是24题这种需要多步重连的题目。6. 给训练营第四天的实战节奏建议与踩坑记录写法6.1 一天四道题怎么安排时间最高效我实际做完这四道题大约花了四个小时其中24题用时最长142题次之。如果时间紧张建议按这个顺序做先做19题删除倒数第N个节点双指针思路有模板可用再做24题两两交换练虚拟头节点然后做02.07链表相交练长度对齐最后啃142环形链表II数学推导需要时间消化。每道题给自己定一个15分钟的最小思考时间不要一上来就看题解。哪怕想不出来也要先写写画画把卡住的点记录下来。15分钟后再看题解理解效率会高很多。6.2 第二天复习时怎么用这四道题查漏补缺训练营的进度很快第四天的内容到第五天如果不复盘基本上会忘掉一半。我的建议是第二天把四道题用新的方法再做一遍比如24题尝试迭代法和递归法各写一次19题尝试两次遍历和双指针各写一次02.07题尝试长度差法和交换遍历法各写一次142题把推导过程默写一遍。写不出来就回头重新看直到能不看题解写对为止。我自己的习惯是准备一个“链表踩坑清单”每做错一次就在对应题目下记一行。比如24题写错过循环条件记下“pre.next and pre.next.next不是cur.next”142题写错过while fast and fast.next记下“第二种循环里不能判断fast.next”。这东西越积累越有价值后期复习比重新刷题高效得多。6.3 一个可以顺手完成的扩展练习如果做完今天这四道题还有余力建议顺手做一道反转链表II用今天的虚拟头节点技巧去处理m到n区间的反转。这道题综合了今天学到的所有要素虚拟头节点、指针备份、区间边界处理。做完之后你会发现明天学反转链表相关题目时今天的底子能让你直接少踩一半坑。