算法训练营第四天，链表专题正式上线。今天的任务很明确：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, val=0, next=None): 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步，还是N+1步？
这里有一个非常经典的细节：要删除倒数第N个节点，正确的做法是让快指针先走N步，然后快慢一起走，快指针到达 null 时停止，此时慢指针指向待删节点的前驱。
为什么不是先走N+1步？如果你想让慢指针直接指向待删节点，那可以让快指针先走N+1步。但删除节点需要前驱，所以让慢指针停在前驱位置更自然。我倾向于用“先走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 恰好指向倒数第N+1个节点。
不删头的场景好理解，删头的场景就考验 dummy 的作用了。假设链表是 1->2，n=2，删除倒数第2个就是删除头节点1。fast 先走2步，指向尾部节点2；开始循环，fast.next为null，循环不执行，slow 还停在 dummy，slow.next.next正好是2，删除成功。如果没有 dummy，slow 初始指向 head，那么 slow 指向1，slow.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 再走 lenB，pB 走完 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当 k=1 时，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.next | fast.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区间的反转。这道题综合了今天学到的所有要素：虚拟头节点、指针备份、区间边界处理。做完之后你会发现，明天学反转链表相关题目时，今天的底子能让你直接少踩一半坑。
