最近集中刷了一批链表和矩阵的题，发现力扣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(m+n) | 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 + b；pB到达交点时，总共走过的距离是b + c + a。
两者完全相等。因为两个指针速度相同，所以它们会在同一时刻到达同一个交点。
如果两个链表没有交点，也就是c = 0，那么：
pA走完a步到达None，切换到headB，再走b步到达None；pB走完b步到达None，切换到headA，再走a步到达None。
最终它们都会停在None，pA == 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：已经反转好的链表的头节点（初始为None）；curr：当前要处理反转的节点（初始为head）；next_temp：curr原本的下一个节点，用于保存现场。
每一步做三件事：
- 保存
curr.next到next_temp； - 把
curr.next指向prev； - 更新
prev = curr，curr = 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 = 1，head.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] | 入口先做两层判断，再取len |
| 240 | 行指针或列指针越界 | 循环条件忘记同时约束r < rows和c >= 0 | 写while r < rows and c >= 0 |
| 160 | 用节点值判断相交 | 不同节点可以有相同val | 必须比较节点对象本身 |
| 160 | 用pA.next is None判断切换 | 对走完链表的时机理解不清 | 直接用pA is None判断切换 |
| 160 | 不理解无交点时的返回 | 双指针最终都变成None | 记住while pA != pB会在空节点处退出并返回None |
| 206 | 先改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，模拟一轮之后你就会发现所有指针操作不过是“保存、修改、移动”这三步的循环。矩阵题也一样，标出当前位置和下一次移动方向，很快就能推导出边界条件。刷题不是背题，把这些底层套路吃透，换多少马甲都不怕。
