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环长度为 bb0。当 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 为 Nonecur 为 head。每一步做四件事先保存 cur.next 到 next再让 cur.next 指向 prev然后整体后移 prev 到 curcur 到 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-2new_head 是 3。此时 head 是 1head.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 headslow 最后停在第二个节点无法断开成两个独立节点。初始为head.next可以保证 slow 停在偏左的位置断开的子链表长度合理。4.5 难点到底在哪进阶39难难在它不是单独考一个算法而是在同一道题里反复切换思维。找中点用的是快慢指针断开链表考验的是对指针引用的把握递归部分考验对归并排序的理解最后合并又回到最基础的链表遍历。任何一个环节不熟整个就卡住。二刷基础91、84之后再做这道题舒服了很多。因为基础91让我刚练完快慢指针的“步长直觉”基础84让我对next指向的修改特别敏感。做排序链表时我在断开那一步明显感觉到如果是上学期一刷完基础题就来做这道题即使会归并排序也会因为指针操作生疏而反复改 bug。4.6 一题串起今天所有的题如果把今天的三道题画成一张知识地图路径是这样的基础91教我用快慢指针找位置基础84教我在移动指针时保持逻辑完整进阶39则让我把前者变成“找中点”把后者变成“断开链表合并操作”。互相咬合得非常紧密。5. 我的“二刷方法论”不是重做一遍而是验证思维路径5.1 如何筛出值得二刷的题我长期维持着一个待办清单每当一道题提交通过后我会给它打一个标签生疏、靠题解、超时、反复改错。只要中了其中一个标签这道题就会排进“两周后二刷”队列。等到二刷那天我不能看任何源码和笔记必须白手起家独立写。这个筛选机制有一个额外的好处它让我对新题的心理压力变小了。因为我知道如果今天没能完全掌握两周后会再有一轮机会修正。5.2 二刷的具体流程我一般按这样的步骤执行拿出题目描述先把输入、输出、约束条件念一遍。用手机计时器开一个 20 分钟的定时完全靠自己思考。如果 20 分钟内没有完整思路就停下来不急着看题解。先去写一个朴素解法哪怕时间复杂度高至少让手先动起来。朴素解法跑通后再想优化方案。写完代码后拿几个测试用例跑一遍重点测边界条件。最后翻看自己一刷时的记录对比差在哪。按这套流程基础91和84分别用了 12 分钟和 8 分钟。一刷时两题加起来用了一个多小时这次快了不少。这个对比本身就是进步的证据。5.3 我用的记录模板每道二刷题我会在表格里记下四样东西题目编号一刷问题二刷用时二刷新体会基础91只想到哈希表不会证明相遇12min证明过程比代码更重要基础84递归返回值理解错8min必须画递归栈图进阶39从未尝试45min快慢指针起点要设为head.next这种表格的威力在于它逼着我把模糊的感受变成明确的语言。很多题做完后我会觉得自己“会了”但真要落笔写“新体会”往往要再想一阵。这个“再想一阵”的过程比重复做一百道新题更有价值。5.4 关于时间安排的建议我不是每天都刷题工作日通常只有晚上 9 点到 10 点能抽出 1 小时。我的安排是前 30 分钟做一道二刷题后 30 分钟攻克新题。如果当天精力尚可就把进阶题也放进来如果状态不好宁可只完成二刷也不去碰新题。有人总担心二刷会拖慢进度会觉得“做新题才是在学东西”。但我的体会完全相反一刷如果只求“代码能跑”你其实是在跟编译器对话二刷时你才有机会跟自己的脑子对话。6. 最后聊点实在的二刷时比较受益的几条经验在二刷基础91和84再啃完进阶39之后有几条感受特别想分享给还在刷题路上挣扎的朋友。首先做链表题时一定要从“地址和引用”的角度去理解不要停留在“节点值”层面。很多人判断链表问题时脑子里全是 val却忘了链表操作的核心是修改 next 指针。二刷反转链表时我一度试图把节点值拿出来重新排列组新链表这虽然能做出来但没有领会反转的真正意图。后来想明白只要把每个节点的 next 方向改一下整个链表就反转了根本不需要新建节点。其次快慢指针不要死记硬背要理解它为什么能解决定位问题。环形链表里的快慢指针是为了追及排序链表里的快慢指针是为了找中点两者都是同一个机制在不同场景下的应用。你把基础91彻底搞透了再做进阶39就会发现很多困难只是“换了一张皮”。最后也是我自己最大的变化我不再追求“今天刷了多少题”而是记录“今天想通了多少个问题”。3月13日这天二刷基础91、84完成进阶39看起来只有三道题但其中有两道是从“背答案”变成了“可推导”一道是从“未知”变成了“啃下来”。对我来说这种进度比一天刷十个 leetcode 标签题要踏实得多。如果你也有一堆“做过但没懂”的题与其急着开新的题单不如挑两三个出来二刷一遍。相信我那种“原来如此”的感觉比提交飘绿的全对更有意思。