链表二刷方法论：从快慢指针到归并排序的进阶之路

3月13日，周五，我的刷题记录上多了一行字：二刷基础91、基础84，完成进阶39。懂行的朋友一眼就明白，这是在链表专题上耗掉了一个下午。今天没开新专题，老老实实把旧题翻出来重新做，又啃了一道进阶题。整个过程谈不上刺激，但恰恰是这种看起来有点“笨”的重复，让我对链表的理解比上周扎实了不少。

1. 为什么我把“基础91、84”列为二刷对象，却给“进阶39”开了先例

1.1 我的刷题清单是怎么编号的

先解释一下标题里的“91、84、39”是什么意思，免得有人以为这是LeetCode题号。我给自己整理的题库分了两个大类：基础百题和进阶五十题。每个专题里的题目按我自己的学习顺序编号，比如基础第91题、基础第84题，进阶第39题。这种编号和难度不直接相关，只代表我整理题目时的先后位置。

后来我发现这种编号方式有个好处：不会因为题目难度产生刻板印象。看到“基础”两个字，很多人会默认它很简单，但实际上有些基础题恰恰是后面所有高级技巧的地基。就像基础84这道反转链表，看起来人人都能背出迭代代码，但真要在白板上从零推导，卡壳的人不在少数。

1.2 为什么要定期“二刷”

我的原则很简单：一道题如果满足以下任一条件，就会被扔进“待二刷”清单：

• 第一次做的时候是照着题解敲出来的，自己并没有独立想通；
• 第一次虽然做对了，但花了超过30分钟，明显卡在某个环节；
• 做了三个月以上，现在让我重新说思路，已经说不清楚了。

基础91和基础84都满足前两条。它们是我刚开始刷链表时遇到的题，当时一头雾水，靠着看别人的代码混过去的。虽然提交通过了，但脑子里的那套逻辑是借来的，不是我自己的。二刷的目的，就是把这套借来的逻辑变成自己的。

1.3 进阶39为什么放在今天

进阶39是“排序链表”。这道题表面上是排序，实际上把快慢指针、归并排序、链表断开与合并这些基础操作全串起来了。它既要用到基础91里的“快慢指针找位置”的思想，也要用到基础84里“反转链表时对指针引用的精细控制”那种手感。所以我刻意把它安排在二刷完这两道基础题之后——先复习基本功，再上手综合题，阶梯感会非常明显。

2. 基础91：环形链表检测，一刷靠“背答案”，二刷才摸到门道

2.1 题目描述

给你一个链表的头节点 head，判断链表中是否有环。如果链表中有某个节点的 next 指针连续指向它之前的节点，那么链表中就存在环。

示例：输入一个 head，第 3 个节点的 next 指向第 2 个节点，返回 true。如果链表完全无环，返回 false。这个问题在面试里出现频率极高，基本属于“必须秒答”的级别。

2.2 两种解法的对比

一刷的时候，我第一反应是哈希表。遍历所有节点，把每个节点的地址存进 set，每走到一个新节点，就检查这个节点之前是否出现过。如果出现过，说明有环。这个做法逻辑上很好懂，时间复杂度 O(n)，空间复杂度 O(n)。提交也能通过，但它有个问题：一旦面试官追问“能不能不用额外空间”，我就哑口无言了。

二刷时我换成了快慢指针。让 slow 和 fast 同时从 head 出发，slow 每次走一步，fast 每次走两步。如果链表无环，fast 会先走到 null，直接返回 false。如果有环，fast 终有一天会在环里追上 slow，因为当两个指针都进入环后，fast 每走两步、slow 每走一步，两者的距离就会缩短 1，必然能相遇。

2.3 代码实现

def hasCycle(head): slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False

这段代码看起来简单，但里面有几个细节非常容易被新手写错。

2.4 一刷时踩过的坑和这次的新认知

一刷时我在循环条件上翻过车。当时写的是while fast.next and slow.next:，导致快指针已经走到尽头时循环还没退出，程序直接报空指针异常。正确的条件应该是判断fast和fast.next是否为空，因为步长是 2，必须确保 fast 能往前跳两步。

二刷时让我真正兴奋的点，不只是背会了快慢指针，而是想通了“为什么一定会相遇”的证明：假设环外长度为 a，环长度为 b（b>0）。当 slow 走到环入口时，fast 已经在环内走了 k 步。两者速度差为 1，每走一轮距离就缩小 1，所以一定会在有限的步数内追上。这个结论我当时在纸上画了一遍才完全放心。

3. 基础84：反转链表，会背迭代并不等于理解指针

3.1 题目描述

给定单链表的头节点 head，反转链表，返回反转后的链表头节点。比如输入 1->2->3->4->5，输出应该是 5->4->3->2->1。

这是链表题里的“hello world”，几乎每个刷题的人都会先碰到它。但很奇怪，很多人在这一题上栽跟头，不是不会写代码，而是稍一追问“递归怎么写？递归过程发生了什么”就开始语无伦次。

3.2 迭代法：用三个指针把方向掰过来

核心思路是维护三个指针：prev、cur、next。初始时 prev 为 None，cur 为 head。每一步做四件事：先保存 cur.next 到 next，再让 cur.next 指向 prev，然后整体后移 prev 到 cur，cur 到 next。循环结束后，prev 就是反转后的新头。

def reverseList(head): prev = None cur = head while cur: next_node = cur.next cur.next = prev prev = cur cur = next_node return prev

第一次写的时候，我总喜欢先移动 cur，再更新 prev，结果链子断在半路。后来我总结出一个小技巧：把这四步想成一个“流水线”，先保存、再改动、再后移。如果不先保存 cur.next，一旦执行cur.next = prev，原先后面的节点就找不到了。

3.3 递归法：从宏观到微观

递归法更短，但理解门槛更高。代码如下：

def reverseList(head): if head is None or head.next is None: return head new_head = reverseList(head.next) head.next.next = head head.next = None return new_head

这里的递归出口是：链表为空，或者只剩一个节点。宏观理解就是“我先把 head 后面的所有节点反转好，再把 head 接到尾巴上”。以 1->2->3 为例：调用 reverseList(2->3)，得到 3->2，new_head 是 3。此时 head 是 1，head.next 是 2，执行head.next.next = head，即 2 的 next 指向 1，然后head.next = None，链表变成 3->2->1。

3.4 二刷才真正搞懂“虚拟头节点”为什么不需要

很多讲解会提到“虚拟头节点”，但反转链表中其实不需要它，因为迭代法中 prev 初始为 None 就是天然的虚拟前驱。二刷时我尝试自己推导了一遍，发现如果不引入虚拟头节点，反转后原链表的头节点会指向 None，那恰好是反转后的最后一个节点。逻辑闭合得很好。

这一题的另外一个收获是：我意识到年初时自己“能默写代码但讲不出过程”是一种假熟练。真正做二刷时，我要求自己必须能从递归调用栈的角度画出示意图，而不是只报出代码。

4. 进阶39：排序链表，一道把所有基础都串起来的难题

4.1 题目描述

给定链表头节点，要求将其按升序排列，并且要求时间复杂度 O(n log n)。数组排序比较简单，但链表没有随机访问，不能直接使用快排的索引，也不能用归并排序里常见的辅助数组。经典解法是“自顶向下的归并排序”，需要三步：找中点、断开链表、分别排序后合并。

示例：输入 4->2->1->3，输出 1->2->3->4。这道题在进阶题单里排第 39 位，我拖了挺久才鼓起勇气去碰它。

4.2 为什么不能直接用数组先转存再排序

一种取巧做法是把链表转成数组，排序后再转回链表。代码好写，但内存占用 O(n)，不符合面试中很多场景下“O(1) 额外空间”的要求。而且这不叫“会排序链表”，只是借助了数组的能力。面试官往往会在你提交后补一句“用常数空间试试”，如果只会数组法就尴尬了。

4.3 核心步骤拆解

第一步：找链表中点。用快慢指针，slow 每次走一步，fast 每次走两步。fast 到末尾时，slow 就停在中点。这和基础91的快慢指针思想完全一脉相承：控制步长差距来定位特殊位置。

第二步：从中点断开链表。这里要注意，不能只把 head 和 mid 记录下来，否则两个子链表还黏在一起。需要找一个 prev 指针，在快慢指针移动时持续记录 slow 前面的节点，最终把prev.next = None断开。

第三步：递归排序两个子链表。递归终止条件为：节点为空或只有一个节点。

第四步：合并两个有序链表。这一步在基础题单里单独出现过，是 merge two sorted lists。我这里不想再写数组拷贝，而是用迭代法逐个比较两个链表当前节点的值，谁小就摘谁。

4.4 完整代码

def sortList(head): if head is None or head.next is None: return head slow = head fast = head.next while fast and fast.next: slow = slow.next fast = fast.next.next mid = slow.next slow.next = None left = sortList(head) right = sortList(mid) dummy = ListNode(0) cur = dummy while left and right: if left.val <= right.val: cur.next = left left = left.next else: cur.next = right right = right.next cur = cur.next cur.next = left if left else right return dummy.next

注意这里有个细节：fast初始时是head.next，而不是head。为什么？因为我们要找的是“前半部分的最后一个节点”，而不是“中点”。比如链表只有两个节点时，如果fast = head，slow 最后停在第二个节点，无法断开成两个独立节点。初始为head.next可以保证 slow 停在偏左的位置，断开的子链表长度合理。

4.5 难点到底在哪

进阶39难，难在它不是单独考一个算法，而是在同一道题里反复切换思维。找中点用的是快慢指针，断开链表考验的是对指针引用的把握，递归部分考验对归并排序的理解，最后合并又回到最基础的链表遍历。任何一个环节不熟，整个就卡住。

二刷基础91、84之后再做这道题，舒服了很多。因为基础91让我刚练完快慢指针的“步长直觉”，基础84让我对next指向的修改特别敏感。做排序链表时，我在断开那一步明显感觉到，如果是上学期一刷完基础题就来做这道题，即使会归并排序，也会因为指针操作生疏而反复改 bug。

4.6 一题串起今天所有的题

如果把今天的三道题画成一张知识地图，路径是这样的：基础91教我用快慢指针找位置，基础84教我在移动指针时保持逻辑完整，进阶39则让我把前者变成“找中点”，把后者变成“断开链表+合并操作”。互相咬合得非常紧密。

5. 我的“二刷方法论”：不是重做一遍，而是验证思维路径

5.1 如何筛出值得二刷的题

我长期维持着一个待办清单，每当一道题提交通过后，我会给它打一个标签：生疏、靠题解、超时、反复改错。只要中了其中一个标签，这道题就会排进“两周后二刷”队列。等到二刷那天，我不能看任何源码和笔记，必须白手起家独立写。

这个筛选机制有一个额外的好处：它让我对新题的心理压力变小了。因为我知道，如果今天没能完全掌握，两周后会再有一轮机会修正。

5.2 二刷的具体流程

我一般按这样的步骤执行：

1. 拿出题目描述，先把输入、输出、约束条件念一遍。
2. 用手机计时器开一个 20 分钟的定时，完全靠自己思考。
3. 如果 20 分钟内没有完整思路，就停下来，不急着看题解。先去写一个朴素解法，哪怕时间复杂度高，至少让手先动起来。
4. 朴素解法跑通后，再想优化方案。
5. 写完代码后，拿几个测试用例跑一遍，重点测边界条件。
6. 最后翻看自己一刷时的记录，对比差在哪。

按这套流程，基础91和84分别用了 12 分钟和 8 分钟。一刷时两题加起来用了一个多小时，这次快了不少。这个对比本身就是进步的证据。

5.3 我用的记录模板

每道二刷题，我会在表格里记下四样东西：

这种表格的威力在于，它逼着我把模糊的感受变成明确的语言。很多题做完后，我会觉得自己“会了”，但真要落笔写“新体会”，往往要再想一阵。这个“再想一阵”的过程，比重复做一百道新题更有价值。

5.4 关于时间安排的建议

我不是每天都刷题，工作日通常只有晚上 9 点到 10 点能抽出 1 小时。我的安排是：前 30 分钟做一道二刷题，后 30 分钟攻克新题。如果当天精力尚可，就把进阶题也放进来；如果状态不好，宁可只完成二刷也不去碰新题。

有人总担心二刷会拖慢进度，会觉得“做新题才是在学东西”。但我的体会完全相反：一刷如果只求“代码能跑”，你其实是在跟编译器对话；二刷时你才有机会跟自己的脑子对话。

6. 最后聊点实在的：二刷时比较受益的几条经验

在二刷基础91和84，再啃完进阶39之后，有几条感受特别想分享给还在刷题路上挣扎的朋友。

首先，做链表题时，一定要从“地址和引用”的角度去理解，不要停留在“节点值”层面。很多人判断链表问题时，脑子里全是 val，却忘了链表操作的核心是修改 next 指针。二刷反转链表时，我一度试图把节点值拿出来重新排列组新链表，这虽然能做出来，但没有领会反转的真正意图。后来想明白，只要把每个节点的 next 方向改一下，整个链表就反转了，根本不需要新建节点。

其次，快慢指针不要死记硬背，要理解它为什么能解决定位问题。环形链表里的快慢指针是为了追及，排序链表里的快慢指针是为了找中点，两者都是同一个机制在不同场景下的应用。你把基础91彻底搞透了，再做进阶39，就会发现很多困难只是“换了一张皮”。

最后，也是我自己最大的变化：我不再追求“今天刷了多少题”，而是记录“今天想通了多少个问题”。3月13日这天，二刷基础91、84，完成进阶39，看起来只有三道题，但其中有两道是从“背答案”变成了“可推导”，一道是从“未知”变成了“啃下来”。对我来说，这种进度比一天刷十个 leetcode 标签题要踏实得多。

如果你也有一堆“做过但没懂”的题，与其急着开新的题单，不如挑两三个出来二刷一遍。相信我，那种“原来如此”的感觉，比提交飘绿的全对更有意思。