1. 一次复盘三道题指针操作的底层逻辑与矩阵排除法的共性昨晚有位准备跳槽的同事把一份刷题清单发给我问哪些题值得放在一起复盘我直接圈出了这三道力扣240.搜索二维矩阵II、160.相交链表、206.反转链表。乍看之下第240题是矩阵搜索第160题和第206题是链表操作好像分属不同专题。但真正把它们逐行写过一遍之后你会发现它们共享同一条思维主线每一步都是通过一次比较或一次指针移动排除掉一部分不可能的解把候选范围不断收紧。区别只在于矩阵题排除的是行或列链表题排除的是节点或长度差。这三道题都是面试里出现频率很高的中等题单独拆开都能写一篇题解。但放到一起刷价值会大得多240题训练的是“在有序结构中找排除路径”160题训练的是“用双指针消除长度差异”206题训练的是“在有限步内重接链表指针”。这三种能力几乎覆盖了算法面试里最常见的推演套路。我这次复盘不打算只给最终解法而是把每一步的思考过程和踩坑点都摊开讲特别适合那种“看过题解能懂、关上答案就写不出来”的读者。另外说明一下本文默认你已经有最基础的链表知识知道next指针是什么能区分“节点引用”和“节点值”。如果你还没到这一步建议先把链表的基础结构过一遍再回来看。下面按题目逐个拆中间会穿插不少我在白板上推演时犯过的错。2. 力扣240 搜索二维矩阵 II右上角出发的“排除法”是怎么一步步想出来的2.1 题目约束比想象中更“松”所以别急着套二分先看清题意。给定一个m x n的矩阵每一行从左到右递增每一列从上到下递增。注意它没有保证前一行的所有值都小于后一行的所有值。举例来说第一行可能是[1, 4, 7, 11]第二行可能是[2, 5, 8, 12]第二行的第一个元素2比第一行的第二个元素4小。这和另一道经典题“每行递增且前一行的末尾小于下一行开头”的严格排序矩阵不一样后者可以把整个矩阵当成一维有序数组做一次二分而本题不行。很多第一次做这题的开发者思路会非常自然地滑向“每一行都二分一下”时间复杂度是O(m log n)空间O(1)。这个解法不是错只是没有把“列也递增”这个条件用足。面试官大概率会追问一句能不能做得更好这时候就该把目光放到“右上角”或者“左下角”这两个特殊位置。为什么特殊因为站在右上角matrix[0][cols-1]时往左走值变小往下走值变大。也就是说这个位置天然把矩阵分成两个方向左边是更小的区域下边是更大的区域。每次拿当前位置和目标值比较只有三种情况相等直接返回True。当前值比目标值大那当前列从当前位置往下都更大更不可能等于目标值整列排除向左移动。当前值比目标值小那当前行从当前位置往左都更小更不可能等于目标值整行排除向下移动。这里的关键不是“移动”而是移动带来的“排除”。一次比较丢掉一整行或一整列最多走m n步就一定能出结果。这就是O(mn)时间复杂度的来源。2.2 把排除过程画出来比背代码有用得多我在白板上通常画一个4 x 4的矩阵来演示1 4 7 11 2 5 8 12 3 6 9 16 10 13 14 24假设目标值是13从右上角11开始。11 13说明第一行的左边所有数不会比11大更不可能等于13。第一行整行排除向下走到16。16 13说明当前列从16往下都大于等于16更不可能是13。第四列整列排除向左走到14。14 13第三列排除向左走到9。9 13第二行排除向下走到13命中。整个过程就像在一个矩形里切蛋糕每次切掉一整条永远不回头。正因为每走一步必然排除一整行或一整列最坏情况也只需要mn次比较不会出现来回横跳的死循环。2.3 参考实现与复杂度边界def searchMatrix(matrix, target): if not matrix or not matrix[0]: return False rows, cols len(matrix), len(matrix[0]) r, c 0, cols - 1 # 从右上角出发 while r rows and c 0: cur matrix[r][c] if cur target: return True if cur target: c - 1 # 排除当前列 else: r 1 # 排除当前行 return False边界情况有三个空矩阵、只有一行、只有一列。空矩阵在开头if not matrix or not matrix[0]已经挡掉只有一行时每次都是列向左移动最终c减到-1退出只有一列时每次都是行向下移动最终r加到rows退出。代码里的while r rows and c 0恰好覆盖所有边界所以不需要在循环体里额外判断。2.4 为什么“从左下角出发”也对但右上角更顺手左下角同样可行向右变大向上变小。两者本质相同时间复杂度也一样。我个人习惯右上角因为在二维数组的直觉里row增大意味着“向下”col减小意味着“向左”这和行、列的排序方向刚好对应写起来不容易把增减方向搞反。你可以各写一遍选自己不容易混的那个。面试里真的会有候选人写着写着把r 1吹成r - 1然后死循环这题调试起来很烦。2.5 和“全局二分”版本的区别如果矩阵满足更严格的约束也就是每一行的末尾都小于下一行的开头那么可以把矩阵拍成一维数组直接二分。我整理了一下两者的差异方便你对比比较项严格排序矩阵可用全局二分本题每行每列递增约束强度每一行末尾 下一行开头无此保证推荐思路映射为一维下标做二分右上角排除法时间复杂度O(log(m*n))O(mn)空间复杂度O(1)O(1)实现难点下标换算方向控制遇到矩阵题先确认约束强度再决定能不能上二分否则很容易写出“看起来对、实际错”的解法。3. 力扣160 相交链表为什么双指针走两次便能相遇3.1 先用“暴力哈希”把正确性垫住相交链表题描述很简单两个单链表可能在某个节点之后合并成一条链找到这个相交节点。特别要注意题目中说的相交是“指针地址相同”不是“节点值相同”。两个链表中各有一个值为3的节点不代表它们相交。最没有脑子的做法是两重循环拿链表A的每个节点去链表B里从头找复杂度O(m*n)通常不是面试官想要的答案。稍微好一点的是哈希集合先遍历链表A把所有节点存入集合再遍历链表B第一个出现在集合里的节点就是交点。时间和空间都是O(mn)。这个版本的代码很直白def getIntersectionNode(headA, headB): seen set() p headA while p: seen.add(p) p p.next p headB while p: if p in seen: return p p p.next return None哈希解法的好处是容易理解、不容易写错而且如果链表有环它也能处理不会死循环。有些面试官只要求这个版本就通过了。但如果你能在哈希之后给出双指针版本并且把证明讲清楚这题的区分度立刻拉满。3.2 双指针版本的推导过程现在考虑双指针。设链表A在交点前的长度为a链表B在交点前的长度为b公共部分长度为c。如果没有交点可以认为c 0也就是最后同时走到None。双指针的做法是pA从headA出发pB从headB出发。两个指针同步走每次各走一步。当pA走到链表A末尾时让它跳到headB当pB走到链表B末尾时让它跳到headA。如果存在交点它们会在交点相遇如果不存在它们会同时走到None。为什么这样能消除长度差看第一轮。假设a 5b 3公共部分c 2。pA先走5步到链表A末尾此时pB已经走完链表B的前3个节点还剩下公共部分的长度为2没有走完也就是它还停在第4个节点上。pA跳到headB继续走pB继续走完公共部分当pB走完整个链表B时pA在链表B上已经补上了b - c 1步的差值。交换之后两个指针分别在两条链上继续走总共走a b步后它们在交点相遇。更直观的理解是pA最终走过的路径是“链表A的全部 链表B从开头到交点的一段”pB最终走过的路径是“链表B的全部 链表A从开头到交点的一段”。两段路径的总长度分别是a (b - c)和b (a - c)注意它俩其实都等于一个公共长度而且最后一步都会落在同一个节点“交点”上。没有交点时c 0两段路径分别是a b和b a长度相同最后同时落在None。3.3 代码写法与“空指针切换”的细节经典代码如下def getIntersectionNode(headA, headB): if not headA or not headB: return None pA, pB headA, headB while pA is not pB: pA pA.next if pA else headB pB pB.next if pB else headA return pA这里有一个细节值得多说两句为什么用pA pA.next if pA else headB而不是pA pA.next因为当pA走到None时它需要跳到另一个链表头。如果你直接写pA.next会报空指针错误。判断条件pA is not pB也很讲究如果两个链表不相交最终两个指针会同时变成NoneNone is None成立循环退出返回None。如果存在交点两个指针在到达交点时地址相同循环退出返回交点。我见过不少人把循环条件写成while pA and pB这样两个指针一旦有一个先到None就停了根本无法处理相交位置在其中一条链很靠后、另一条链很短的情况。这是最容易踩的坑。3.4 有环链表对双指针的威胁双指针解法默认链表是无环的。如果链表里有环这个“走到底跳另一条链”的思路可能陷入无限循环因为你永远走不到None。哈希解法在这种情况下依然安全。如果你不确定面试官给的是不是无环链表可以先用快慢指针判环或者直接用哈希解法兜底。刷题网站上的原题会明确说明链表无环但口头面试时最好确认一句能体现你思考过边界。4. 力扣206 反转链表迭代指针绕线与递归“归去来兮”4.1 为什么会需要三根指针两根行不行反转链表要求把1 - 2 - 3 - None变成3 - 2 - 1 - None。很多新手卡在这里是因为没有理解“修改next指针会丢失原本的后续节点”。假设当前在节点1你要让1.next指向None。直接执行head.next None之后节点2和3就再也找不到了。所以必须有一个额外的指针在覆盖next之前先把后面的链表头保存下来。这就是三根指针的由来prev记录前面已经反转好的部分curr记录当前要处理的位置nxt保存curr.next以防丢失。代码实现是def reverseList(head): prev None curr head while curr: nxt curr.next # 先记住下一站 curr.next prev # 调转方向 prev curr # 前指针前进 curr nxt # 当前指针前进 return prev退出的时刻是curr变成None这时prev正好指向原链表的最后一个节点它就是反转后链表的头。边界条件很自然空链表直接返回None只有一个节点时循环执行一轮curr.next指向None最后prev还是那个唯一节点返回它。所以这个实现不需要额外写if not head or not head.next的单独分支循环天然处理了。4.2 递归版的核心先相信子问题已经完成递归法的思维路径不太一样。先写出口def reverseList(head): if not head or not head.next: return head new_head reverseList(head.next) head.next.next head head.next None return new_head递归出口解决了两件事空链表和只有一个节点的链表。这两种情况反转结果都是自身直接返回。递归的核心在head.next.next head。假设输入是1 - 2 - 3 - None先递归反转从2开始的后半段得到3 - 2 - None此时返回的new_head是节点3。回到外层当前head是节点1head.next是节点2。执行head.next.next head也就是2.next 1把节点1接到节点2后面形成3 - 2 - 1。然后head.next None把节点1原本指向节点2的旧连接断掉避免环。最后返回new_head。很多初学者卡住是因为潜意识里认为“递归一旦进去了后面的代码不会执行”。实际不是这样递归是“先纵深进去再逐层返回时执行后面的代码”。你只需要信任reverseList(head.next)已经正确处理了后半段然后处理当前节点和后一个节点之间的关系剩下的交给递归。这种“归去来兮”的节奏可以通过画三层调用的展开图来体会。4.3 两种写法的对比与真实面试场景的选择迭代和递归各有取舍我用下面这张表总结了一下比较项迭代三指针递归反转空间复杂度O(1)递归栈O(n)可读性指针操作多容易晕代码简短思路清晰长链表风险无链表过长时可能爆栈面试推荐度更稳面试官要求时再用我自己在线下模拟面试时看到过不少候选人写了递归却在“谁能被安全地反转”这类问题上翻车相反把三指针画清楚的人通常很快就能写对。所以我的建议是默认先练熟迭代版递归版能讲清楚原理即可。如果你的目标公司明确喜欢递归思维那就把递归版也练到闭眼能写。这道题还有一个进阶版反转链表中的某一段区间核心逻辑是一样的只是多了定位两个边界节点和对边界指针的额外处理。先把基础版吃透后面进阶会顺畅很多。5. 集中复盘带来的三条通用经验与面试输出顺序5.1 经验一链表题在动指针之前先问自己“原next丢了吗”把206和160放在一起看会发现一个共同铁律链表操作里每一次修改next本质上都是在“断线重连”。断了线之后如果还有后续节点要访问那它们必须在修改之前提前保存。206里的nxt curr.next是这个原则的直接体现160里两个指针之所以能在换链时不迷路也是因为每一步都踩着旧的next往前推进只是没有修改指针而已。我复盘时常用的自检动作是每写一行xxx.next yyy就绕着链表演一遍“如果我现在站在这行代码之前我还能不能找到原来的下一个人”。如果找不到说明少保存了一个指针。5.2 经验二从右上角排除矩阵本质也是一种“缩小候选集”矩阵题和链表题看起来毫不相干但240题的“排除一行/列”和160题的“消除长度差”底层都是同一个思想找到问题的某个不变量让每次操作都严格缩小搜索空间。矩阵的右上角左侧一定比当前位置小下面一定比它大链表双指针则保证两条路径总长度相同从而某个时刻两者必然同点相遇。面试中的难题几乎都是这一类“利用结构性约束缩小范围”的变体。5.3 经验三面试时的输出顺序比最终代码更影响评价我模拟面试时会刻意训练候选人按下面顺序输出效果普遍很好先读题确认输入输出、边界条件空矩阵空链表单节点有没有环。给一个暴力解法或最简单解法把正确性讲清楚哪怕它不是最优。再分析暴力解法慢在哪引申出优化方向。最后写最优解法并在写前说出时间复杂度和空间复杂度。写完代码后手动用一个小例子走一遍关键循环而不是直接说“我觉得应该没问题”。比如160题我会先说哈希集合法它简单直观然后说“如果面试官希望空间也是O(1)我可以用双指针”再顺势推到双指针。这样做的好处是即使面试中误判了最优解面试官至少认为你有清晰的思考路径而不是背了一个答案。240题也一样先承认“每行二分”是有效的再优化到排除法表现会好很多。5.4 复盘之后可以顺势练习的扩展题如果你刷完这三道题还有余力建议按同一套思维模式去碰下面几个比较经典的变体反转链表 II只需要反转链表中间一段看你能不能保留住边界指针。环形链表快慢指针判环这其实和双指针的“追赶相遇”是同一个套路。合并两个有序链表同样是链表指针重接锻炼“同时追踪两个头”的感觉。有序矩阵中的第K小元素矩阵搜索的进阶需要结合堆和二分。寻找重复数数组里的“环形链表”思想利用下标映射成环来定位重复值。这几道题会反复用到“缩小候选范围”和“指针重连”的思维算是三者融合后的进阶练习。最后再分享一个小细节这次复盘我自己最大的收获不是记住了每道题的代码而是整理出了一套“动手前先问结构约束”的习惯。拿到任何算法题先不急着写循环而是问三句话数据结构的边界在哪每一步能确定排除掉什么操作之后不变量还成立吗这三句话放在240、160、206上都成立放到其他题上也同样成立。你下次刷题时不妨也带着这三个问题去。