最近集中刷了一批链表和矩阵的题发现力扣240、160、206这三道题放在一起特别有意思一个考“有序数据结构的搜索路径”一个考“链表的拓扑关系”一个考“指针重连的基本功”。它们都没有复杂的算法模板却能把人的思维从暴力解逼到最优解。这篇文章就按我自己的刷题顺序把这三题的完整思考、代码实现、复杂度分析和踩坑点写出来尤其适合那些刚学完数据结构、正准备开始刷题的朋友。1. 力扣240搜索二维矩阵II——一趟走完一行和一列1.1 题目长什么样以及为什么不能整体二分力扣240题给定一个m x n的矩阵要求满足每一行从左到右升序排列每一列从上到下升序排列要求查找目标值target是否存在于矩阵中。比如常见的例子[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]查找5返回true查找20返回false。第一次看到这题很多人会想矩阵行列都有序是不是能像力扣74题那样把整个矩阵“拉平”成一个一维有序数组直接二分注意74题说的是“每一行升序且下一行的第一个元素大于上一行的最后一个元素”那是严格的整体有序确实可以拉平。但240题没有这个保证比如第一行末尾的15大于第二行开头的5第二行末尾的19也大于第三行开头的3可是整体并不是从小到大连续排列的。如果直接拉平二分时你会丢失“列方向也有序”这个重要条件。那能不能对每一行分别做二分可以复杂度是O(m log n)在行数不多时也是能接受的。但题目真正想考察的其实是一个从右上角出发、每次排除一整行或一整列的线性解法时间复杂度O(m n)。这个解法在面试里才是最有区分度的答案。1.2 从右上角开始的排除法——为什么它能一次砍掉一行或一列过来人可能都听过一句话“搜索二维矩阵II从右上角开始走。”很多人记住了位置但没想明白为什么。我尽量一次讲清楚。在任意一个位置(r, c)上当前元素matrix[r][c]同时受到两个方向约束因为这一行从左到右递增所以当前元素的左侧所有元素都小于等于它因为这一列从上到下递增所以当前元素的下方所有元素都大于等于它。如果我从矩阵右上角(0, n-1)开始此时当前元素就是第一行最大的数、最后一列最小的数。接下来比较target和matrix[r][c]如果target matrix[r][c]直接返回true如果target matrix[r][c]说明target不可能出现在当前元素所在的这一列。因为这一列从上到下递增当前元素已经是这一列里最小的了比它小的目标值只会更靠左。于是我可以把c向左移动一位排除整列如果target matrix[r][c]说明target不可能出现在当前元素所在的这一行。因为这一行从左到右递增当前元素已经是这一行最大的了比它大的目标值只会更靠下。于是我可以把r向下移动一位排除整行。每次都排除一整行或一整列走的总步数不会超过m n所以时间复杂度是线性的。这就是这个解法的核心逻辑。那为什么不能从左上角开始呢因为左上角是整行整列的最小值如果target比它大你可能向下、向右都有可能无法做出唯一判断右下角也同理。右上角和左下角才是“行最大、列最小”或“行最小、列最大”这样的分岔点能让每一次比较都有确定性。1.3 代码实现、边界处理和复杂度分析Python 代码非常简洁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: if matrix[r][c] target: return True elif matrix[r][c] target: c - 1 else: r 1 return False这里必须注意两个边界先判断not matrix再判断not matrix[0]。因为空矩阵matrix []时访问matrix[0]会直接越界while r rows and c 0的循环条件缺一不可。如果写成while r rows列指针可能变成-1如果只写c 0行指针可能越界。也可以从左下角出发代码对称def searchMatrix(matrix, target): if not matrix or not matrix[0]: return False rows, cols len(matrix), len(matrix[0]) r, c rows - 1, 0 while r 0 and c cols: if matrix[r][c] target: return True elif matrix[r][c] target: r - 1 else: c 1 return False注意这里判断方向正好相反当前元素是这一行最大的、这一列最小的所以target更小就向上走target更大就向右走。空间复杂度是O(1)只用了两个指针。时间复杂度是O(m n)因为最坏情况下行指针从0走到m-1列指针从n-1走到0合计最多m n步。1.4 几种解法的对比与选型建议我把这道题常见的几种解法放在一起对比解法时间复杂度空间复杂度适用场景暴力遍历O(m*n)O(1)矩阵极小或者只想快速验证思路逐行二分O(m*log n)O(1)行数少、列数多的矩阵代码容易写右上/左下排除法O(mn)O(1)最推荐面试、竞赛都够用二分分割法O(m*log(n/m)) 或更复杂O(log n)追求理论最优但实现复杂不推荐日常刷题我个人强烈建议优先掌握右上/左下排除法。它不依赖二分模板却比二分更能体现“充分利用有序性”的思维。如果你的目标是准备面试这个解法是标准答案如果你的目标是练习二分再单独去刷74题会更有针对性。2. 力扣160相交链表——两个指针走完彼此的“弯路”2.1 题目描述与直觉陷阱力扣160题要求给定两个单链表的头节点headA和headB找出两个链表相交的起始节点。如果两个链表没有交点返回null。题目有一个很关键的定义相交指的是节点引用相同而不是节点值相同。很多第一次做的人在这里就会踩坑自认为两个val相等的节点就是交点结果发现测试用例里有两条链表都包含值为3的节点但这两个节点其实是不同的对象。最朴素的解法是遍历链表A把所有节点存进一个哈希集合再遍历链表B逐个判断当前节点是否出现在集合里。第一个出现的就是交点。这个解法的时间复杂度是O(m n)空间复杂度是O(m)。如果面试官继续追问“能不能不用额外空间”就需要双指针法了。这道题的直觉障碍在于两条链表长度不一样如果只是同时从各自的头节点往后走根本不可能同时到达交点。最常见的错误想法是“我先数出两条链表的长度差把长的那个先走几步让它们对齐再一起走”。这也是可行解但需要先求长度、再移动写起来要多一遍遍历。双指针法更漂亮它通过“互相交换接力”来消除长度差。2.2 双指针法原理与严格证明双指针解法代码很短但很多人第一次看到会觉得很神奇def getIntersectionNode(headA, headB): pA, pB headA, headB while pA ! pB: pA pA.next if pA else headB pB pB.next if pB else headA return pA为什么两个指针最终会相遇我们来证明一下。设链表A的独有部分长度为a链表B的独有部分长度为b公共部分长度为c。那么指针pA从headA出发走完a c步到达链表尾部指针pB从headB出发走完b c步到达链表尾部如果两个链表相交c 0如果不相交c 0。当pA走完链表A后让它切换到headB继续走当pB走完链表B后让它切换到headA继续走。这样pA到达交点时总共走过的距离是a c bpB到达交点时总共走过的距离是b c a。两者完全相等。因为两个指针速度相同所以它们会在同一时刻到达同一个交点。如果两个链表没有交点也就是c 0那么pA走完a步到达None切换到headB再走b步到达NonepB走完b步到达None切换到headA再走a步到达None。最终它们都会停在NonepA pB None循环结束返回None符合预期。这个过程可以理解为两个人都走了“自己的路 对方的路”路程相同时终点的位置必然相同。2.3 容易翻车的三个细节我把这道题的高频错误整理了一下每一个都是我实际刷题时看别人踩过、或者自己踩过的把节点值当作节点本身。两个不同节点可以拥有相同的val所以判断pA.val pB.val是完全错误的。必须比较对象本身Python 中直接比较pA pB实际上调用的也是对象地址级比较默认没有重载__eq__可以放心用判断pA.next而不是pA是否为空。很多人会把切换逻辑写成while pA ! pB: pA pA.next if pA.next else headB pB pB.next if pB.next else headA这个写法在链表长度为1时很容易出问题。更标准、更安全的写法是判断pA本身是否为空而不是pA.next是否为空。原因在于当pA正好是尾节点时pA.next已经是None此时应该切换到对方链表头部而不是让pA继续往下走一步变成None后再切换。两种写法最终结果可能一样但判断pA.next的代码在长度极端情况下更绕还容易在无交点场景中提前退出导致返回错误节点 3.忘记处理空链表。如果headA或headB是空循环直接不进入返回None这其实是正确行为不需要额外加判断但你要能向面试官解释清楚这一点。2.4 如果面试官让你先求长度差该怎么写双指针法虽然巧妙但并不是唯一方案。有时候面试官会引导你先求两条链表长度再让长链表先走“长度差”步最后两个指针同步前进。这个思路更符合直觉我建议也要能写出来def getIntersectionNode(headA, headB): 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 ! pb: pa pa.next pb pb.next return pa这种解法同样时间复杂度O(m n)空间复杂度O(1)只不过要比双指针法多遍历一次链表。双指针法的优点是一遍遍历里同时完成“长度对齐”和“查找交点”代码更短但理解门槛稍高。两种方法都建议掌握面试时可以根据对方的提问习惯灵活选择。3. 力扣206反转链表——指针重连的基本功3.1 迭代反转三指针各司其职力扣206要求反转一个单链表输入1 - 2 - 3 - 4 - 5输出5 - 4 - 3 - 2 - 1。这是链表操作里最基础的题也是后续反转区间、K个一组翻转的前置技能。迭代法的核心思想很暴力从头开始把每个节点的next指针从“指向后一个节点”改成“指向前一个节点”。但改掉一个指针之前必须先把它的下一位保存下来否则链表就断了。所以我们需要三个指针prev已经反转好的链表的头节点初始为Nonecurr当前要处理反转的节点初始为headnext_tempcurr原本的下一个节点用于保存现场。每一步做三件事保存curr.next到next_temp把curr.next指向prev更新prev currcurr next_temp整体向后移动。循环直到curr为空此时prev正好是原链表的最后一个节点也就是反转后链表的头节点返回prev。代码如下def reverseList(head): prev None curr head while curr: next_temp curr.next curr.next prev prev curr curr next_temp return prev这里最容易犯的错误是先写了curr.next prev再去取curr.next存next_temp结果next_temp变成了prev链表后半部分全部丢失。记住一句话先保存后修改。3.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其实拆成两步就懂了假设head.next以及后面的子链表已经全部反转完成reverseList(head.next)返回的是原链表尾节点也就是新链表的头节点现在要让当前节点head接到子链表反转后的尾部。因为子链表已经反转原head.next这个节点现在变成了子链表的最后一个节点它的next正好是None或者指向原后面的节点不反转后它的next已经变成了它的前一个节点。为了让head成为新的尾节点需要把head.next.next指向head。画一个两个节点的例子最直观链表1 - 2。调用reverseList(1)head 1head.next不为空所以先递归调用reverseList(2)head 2时head.next为空返回2此时new_head 2回到上一层head 1执行head.next.next head就是2.next 1执行head.next None就是1.next None返回new_head 2得到2 - 1。对于更长的链表过程完全一样每次递归返回的都是“子链表反转后的新头”然后当前节点作为新尾接进去。递归的优点是代码简洁、思维集中在子问题上缺点是需要额外的递归栈空间O(n)。如果链表长度很大可能会栈溢出如果面试官明确要求O(1)空间就一定要用迭代法。3.3 迭代与递归的边界条件对比条件迭代法递归法空链表返回None直接跳过循环返回None命中not head单节点链表返回原节点返回原节点命中not head.next空间复杂度O(1)O(n)修改原链表会会理解门槛指针跳跃需要画图子问题抽象需要想清楚“当前步”我的建议是两个都写熟。迭代法作为默认答案因为不额外占栈空间递归法用来检验自己是否真正理解了链表结构也能在面试中展示思维广度。3.4 一个很容易忽略的 Bug置空原头节点的 next在递归解法里head.next None这行非常重要。如果忘记置空那么原头节点仍然指向原第二个节点而原第二个节点在反转后又指向了原头节点于是链表会形成一个环造成死循环。迭代法里prev初始是None当处理原头节点时curr.next prev已经是把原头节点的next置为None了所以不需要额外处理。但递归法的最后一步必须手动置空这一点差之毫厘、谬以千里。4. 三道题放在一起怎么练——刷题策略、错误排查与个人体会4.1 从暴力到最优三道题共通的思维升级路径单独刷这三道题可能觉得它们没什么关系。但放在一起看能发现一个共性所有最优解都利用了“当前状态”与“剩余搜索空间”之间的约束关系。240题右上角的元素同时是行最大、列最小所以每次比较都能排除一整行或一整列160题两个指针各自走完“自己的路 对方的路”之后路程差被抹平从而能够同时到达交点206题反转的本质是让每个节点的next从“指向未来”变成“指向过去”但过程中必须保住“未来”的现场。暴力解法往往只是无脑枚举最优解则是在枚举过程中找到一条“每次都能排除一部分”的路径。这个思维从矩阵搜索到链表操作都适用。4.2 常见错误与调试技巧速查表刷题过程中错误不可避免。我把这三道题最常见的错误按“症状 - 原因 - 解法”整理成一张速查表方便你复习时对照。题目典型错误根本原因解决方式240从左上角开始搜索左上角元素太小目标更大时无法确定往右还是往下从右上角或左下角出发保证能排除整行/整列240空矩阵matrix []越界没判断not matrix或not matrix[0]入口先做两层判断再取len240行指针或列指针越界循环条件忘记同时约束r rows和c 0写while r rows and c 0160用节点值判断相交不同节点可以有相同val必须比较节点对象本身160用pA.next is None判断切换对走完链表的时机理解不清直接用pA is None判断切换160不理解无交点时的返回双指针最终都变成None记住while pA ! pB会在空节点处退出并返回None206先改curr.next再保存next_temp执行顺序错误导致链表断裂每一轮先把next_temp curr.next保存好206递归忘记head.next None原头节点仍指向第二个节点形成环递归每一层最后必须把当前节点指向空调试时我建议多用小规模测试用例比如[1]、[1,2]、[1,2,3]。不要一上来就跑大用例小数据能让你手动模拟每一步指针变化。对于链表题我还会在代码里临时加打印输出每一轮prev、curr、next_temp的值一旦发现某一步出现重复节点基本就是环产生了。4.3 我的实操心得与后续扩展这三道题给我最大的收获是养成了一个习惯写代码前先想清楚“循环不变式”。240的循环不变式是target只可能存在于当前矩阵的右下角子矩阵中从右上角出发时实际是“已排除左上角区域”后的剩余区域160的循环不变式是pA和pB如果想要相遇它们需要走的路程差正在被逐渐抹平206的循环不变式是prev始终是已经完成反转的部分链表的头节点curr始终是尚未处理的部分链表的头节点。有了不变式写代码就像有了导航每一步操作后都检查一下“这个性质还成立吗”如果成立代码大概率就是对的。把这组题刷完之后可以继续做这些扩展题240的进阶力扣74题“搜索二维矩阵”它的矩阵是严格整体有序真正可以用一维二分160的进阶力扣141、142题“环形链表”以及“环形链表 II”需要用到快慢指针和数学推导206的进阶力扣92题“反转链表 II”、力扣25题“K 个一组翻转链表”它们是206题的直接扩展理解了206的指针操作后再去看区间反转就会顺畅很多。最后再分享一个小经验遇到链表题先不要急着写代码拿笔在纸上画三个方框代表prev、curr、next_temp模拟一轮之后你就会发现所有指针操作不过是“保存、修改、移动”这三步的循环。矩阵题也一样标出当前位置和下一次移动方向很快就能推导出边界条件。刷题不是背题把这些底层套路吃透换多少马甲都不怕。