南瑾i周日早上九点，我照常打开日常打卡页面。今天是第23天，题目单上写着“双指针 & 链表 & 回溯算法”，一共6道题。这三个词几乎是算法面试里的钉子户：数组操作靠双指针，链表操作考指针稳定性，回溯算法则是递归思维的试金石。放在同一天打卡，看起来像是随机拼凑，实际刷完就会发现，它们其实都在回答同一个问题——怎么用最少的额外空间、最清晰的状态管理，把暴力解法梳理成有章法的代码。这篇文章就记录我当天的完整刷题过程和踩坑记录，适合刚开始系统刷算法、或者刷了几个月但总在链表和递归上卡壳的朋友，也适合准备面试前想快速过一遍高频题型的人。
1. 今日题目总览与选题思路
1.1 为什么把双指针、链表、回溯放在同一天打卡
先说结论：这三类题放在一起不是巧合，而是刷题路线上一个很自然的递进组合。
双指针处理的是“线性结构上的双路遍历”，链表处理的是“指针关系上的节点操作”，回溯算法处理的是“多分支状态下的递归搜索”。三者分别代表数组、链表、树形搜索三类完全不同的数据组织方式。一天内同时接触三种形态，能强迫大脑在“下标思维”“节点思维”“递归思维”之间快速切换，这种切换能力恰恰是面试中最需要的。
我之前刷题是分成专题周来搞的，比如这一周全刷链表，下一周全刷回溯。这么做有一个问题：相邻题目太相似，写代码的时候容易形成肌肉记忆，刷完感觉会了，隔两周再看同一道题反而想不起来思路。后来我改成混合打卡，相邻两天尽量安排不同主题，再每隔几天回刷一次旧题，记忆留存率明显高了不少。今天这组题就是按这个思路挑的。
1.2 六道题怎么选、难度阶梯怎么排
我选的6道题如下，每个主题内部都保持“入门题 + 经典进阶题”的结构：
- 双指针：删除有序数组中的重复项（快慢指针入门）、三数之和（左右指针经典）
- 链表：反转链表（指针操作基础）、环形链表 II（快慢指针 + 数学推导）
- 回溯：全排列（回溯模板入门）、组合总和（回溯剪枝进阶）
难度的安排也有讲究。如果把三道难题放在当天前半段，非常容易受挫。我习惯把每个主题内的简单题放在前面，先用短平快的AC建立信心，再进入需要推导的题目。比如链表的两题，反转链表我大概5分钟写完，环形链表 II光推导相遇就花了20分钟，如果顺序反过来，可能一开始就卡住不想刷了。
1.3 打卡前的自查清单
每次打卡前我会花两分钟做一次自查，避免坐在电脑前无脑打开题目：
- 今天涉及的数据结构是什么？数组、链表、还是递归树。
- 我上一次刷这类题是什么时候？如果超过一周，先花5分钟翻旧题的代码。
- 今天的目标是什么？是AC就行，还是必须把复杂度降到最优，还是练习手写模板。
这个习惯帮了我很大忙。比如今天链表的两道题属于“指针操作”类型，我翻了一下上周写的合并两个有序链表的代码，脑子里先恢复了一遍“dummy节点”和“指针断开顺序”的记忆，再去做反转链表，顺畅很多。
| 主题 | 入门题 | 进阶题 | 核心练习点 |
|---|---|---|---|
| 双指针 | 删除有序数组中的重复项 | 三数之和 | 边界条件、去重 |
| 链表 | 反转链表 | 环形链表 II | 指针稳定性、数学推导 |
| 回溯 | 全排列 | 组合总和 | 状态回退、剪枝 |
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 双指针：边界条件才是真正的考点
2.1 第一题：删除有序数组中的重复项
题目要求原地删除重复元素，返回新长度。不允许用set，不允许开新数组。我第一眼看到“原地”这两个字，就知道这道题想考快慢指针。
慢指针负责维护“已经处理好的不重复区间”的末端，快指针负责向后扫描。每当快指针遇到一个和慢指针所在位置值不同的元素，就把它搬到慢指针的下一个位置。代码写起来很简单：
python复制def removeDuplicates(nums):
if not nums:
return 0
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
这里最关键的判断是 if nums[fast] != nums[slow]，不是和 nums[fast-1] 比，也不是和某个“上一个值”比。为什么用 nums[slow]？因为 nums[slow] 始终是当前不重复区间的最后一个元素，快指针扫描到的值如果和它不同，说明出现了新元素。如果用 nums[fast-1] 做比较，在已经有多个重复值的情况下也能成立，但语义上不如 nums[slow] 直观，而且一旦题目改成“最多保留两个重复值”，nums[fast-1] 的写法就不容易扩展了。
我第一遍写这道题时犯过一个低级错误：循环结束后直接返回 slow，忘记了 slow 是索引而不是长度。索引0代表第一个元素，所以长度必须加1。这种“索引和长度差1”的错在双指针题里太常见了，尤其写快慢指针的时候，一定要在返回前想清楚变量表示的是位置还是个数。
2.2 第二题：三数之和
三数之和是双指针里最经典的题之一。暴力三重循环是O(n^3)，面试官肯定会追问优化。标准解法是：先排序，固定一个数，再用左右指针在剩余区间里找和为目标的组合。排序让数组有序，左右指针才可以根据当前和的大小决定往哪个方向移动。
去重是这题的重灾区。我当时写完代码跑测试用例，发现输出里有重复的三元组。怎么改都不对，最后才意识到：去重的对象有两个层级。第一层是外层固定的数不能重复，第二层是左右指针移动时要跳过值相同的元素。代码里对应两个判断：
python复制def threeSum(nums):
nums.sort()
n = len(nums)
res = []
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
res.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
elif total < 0:
left += 1
else:
right -= 1
return res
外层去重用 nums[i] == nums[i-1]，这个写法很讲究：是和前一个已处理过的值比较，不是和后一个值比较。如果用 nums[i] == nums[i+1]，会跳过第一组有效解。内层指针的去重则是在找到一个合法三元组之后，跳过所有值相同的元素，防止同一个组合反复出现。
我第一次做的时候把去重写在了 total < 0 和 total > 0 的分支里，结果在 [-1, -1, 2] 这种用例上反复出错。后来想明白了：去重的前提是已经找到合法结果，不需要在探索过程中提前跳，否则会漏解。这两者的区别我得在代码注释里标清楚。
2.3 双指针题的debug心得和边界表
双指针题写错，90%是边界条件没想清楚。我整理了一张速查表：
| 问题场景 | 循环条件 | 常见坑 |
|---|---|---|
| 快慢指针遍历数组 | fast < n |
返回长度时忘记索引+1 |
| 左右指针相向扫描 | left < right |
用 left <= right 导致越界 |
| 合并两个有序数组 | 一个指针走完后处理剩余 | 忘了把剩余元素追加 |
| 滑动窗口 | right 先扩，left 再缩 |
窗口收缩时机不对 |
还有一个经验：双指针题不要背模板，要画。我是在纸上画“指针移动轨迹”才真正理解快慢指针的。画的时候把快指针每走一步的数组状态都写下来，慢指针的变化一目了然。特别是“先判断再移动”还是“先移动再判断”这类顺序问题，画一遍就清楚了。
3. 链表：指针操作容易把脑子绕进去
3.1 第三题：反转链表
反转链表的迭代版几乎是面试必考，代码很短，但很多人写的时候指针顺序总乱。核心就一句话：断链之前先记下 next。
三步走：先保存 curr.next，然后把 curr.next 指向 prev，再把 prev 和 curr 整体后移。很多人写错是因为在一个链表节点上连续操作，忘了保存原始的 next，导致链表后半截丢失。看代码：
python复制def reverseList(head):
prev = None
curr = head
while curr:
next_node = curr.next # 先记下后继
curr.next = prev # 反转指针
prev = curr # prev 前移
curr = next_node # curr 前移
return prev
递归版需要理解一个反直觉的点：递归处理的是子链表，返回的是新链表的头，但当前层要做的工作是把当前节点接到子链表反转后的尾部。这个“尾部”其实就是 head.next 递归反转后，原来 head 的 next 变成了新链表的最后一个节点。所以代码是：
python复制def reverseListRecursive(head):
if not head or not head.next:
return head
new_head = reverseListRecursive(head.next)
head.next.next = head
head.next = None
return new_head
head.next.next = head 这一行很多人看不懂。我当时的理解方式：head.next 是旧链表中处于 head 后面的节点，递归反转之后它变成了新链表的尾部，所以让“这个尾部节点的 next”指向 head，正好把 head 挂在后面。想明白这一点之后，递归版就再也不用背了。
3.2 第四题：环形链表 II
这道题要找到环的入口，用快慢指针。快指针每次走两步，慢指针每次走一步，如果链表有环，两指针必然相遇。难点在于相遇之后怎么找入口。
这里有一段必须自己推导的数学过程。设链表头到环入口的距离是 a，环入口到相遇点的距离是 b，此时慢指针走了 a + b。快指针速度是慢指针两倍，所以快指针走了 2(a+b)。同时快指针已经在环里多走了若干圈，设环长为 c，则有：
code复制2(a+b) = a + b + n*c
a + b = n*c
a = n*c - b
这个式子说明：从相遇点继续走，再走 a 步，恰好回到环入口。所以我们让一个指针从链表头开始走，另一个指针从相遇点开始走，两者速度相同，走 a 步后必然在环入口相遇。这个推导我每次都会当场算一遍，算完再写代码，出错概率就低了。
python复制def detectCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
p = head
q = slow
while p != q:
p = p.next
q = q.next
return p
return None
注意循环条件 fast and fast.next 要同时判断，否则如果链表无环，直接访问 fast.next.next 会空指针异常。还有一个细节：相遇之后第二阶段判断的是“是否到达入口”，判断条件是 p != q，不是 p.next != q.next，后者在入口相邻的特殊情况下会死循环。
3.3 链表题的黄金法则：画图、哑节点、换行检查
链表题最容易犯的错不是算法不会，而是指针连连看的时候把自己绕进去。我总结出三条实操法则。
第一，画图。任何链表题开写之前，先在草稿纸上画一个三节点链表，标明每个节点的地址值和next指向，然后手动模拟指针操作。三节点够用，因为指针操作最多跨越三个相邻节点。
第二，善用哑节点。凡是可能删除头结点、或者在头部插入的题，都先创建一个dummy节点，让 dummy.next = head，最后返回 dummy.next。这样头结点就退化成普通节点，不需要单独处理边界。环形链表那题不需要dummy，但反转链表、删除倒数第N个节点这类题没它不行。
第三，写完后做一轮“断链检查”：从 head 开始，沿着next一步一步走，看是否访问了已断开的旧指针。我刷反转链表时经常出现一种错误：prev 和 curr 移动顺序写反，导致链表虽然没丢节点，但形成了子环。这种错很难在脑内模拟的时候发现，最好是把每一步之后的链表状态列出来，对照原始链表逐节点核对。
3.4 链表操作速查表
把链表常见题型的核心解法整理成一张表，方便复习：
| 题型 | 核心技巧 | 复杂度 | 关键注意点 |
|---|---|---|---|
| 反转链表 | 三指针迭代/递归 | O(n), O(1) | 先存 next 再断链 |
| 找中间节点 | 快慢指针 | O(n), O(1) | fast 一次走两步 |
| 判断是否有环 | 快慢指针 | O(n), O(1) | fast 走两步，注意空指针 |
| 找环入口 | 快慢指针 + 数学推导 | O(n), O(1) | 相遇后新指针从头再走 |
| 删除指定节点 | 哑节点 + 前驱指针 | O(n), O(1) | 别忘记处理尾节点 |
| 合并有序链表 | 哑节点 + 双指针 | O(n), O(1) | 循环结束补充剩余链表 |
这张表做完，后面刷 LRU、回文链表、排序链表的时候，直接对照表里的指针操作套路，能省不少事。
4. 回溯算法：本质上是在遍历一棵决策树
4.1 第五题：全排列
回溯算法的本质是对决策树做深度优先遍历。每到一个节点，我们做一个选择，进入下一层，再撤销这个选择。全排列是最标准的入门题，因为选择列表就是“还剩哪些数没用过”。
我用的是模板化写法：path 表示当前路径，used 数组记录哪些数已经用过，循环里遍历所有候选数，对没用过的数做选择。递归结束条件是 len(path) == len(nums)。
python复制def permute(nums):
def backtrack(path, used):
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
path.append(nums[i])
backtrack(path, used)
path.pop()
used[i] = False
res = []
backtrack([], [False] * len(nums))
return res
这里有一个几乎所有初学者都会踩的坑：直接 res.append(path) 会把当前 path 的引用加入结果，后续回溯撤销选择时，path 被修改，已经存入 res 的列表也会跟着变。必须写 path[:] 或者 list(path) 做一次拷贝。我当时debug的时候打印 res，发现里面全是同一个空列表，排查了半天才意识到这是引用问题。在Python里这个问题尤其隐蔽，其他语言如果传的是引用也会有同样的坑。
全排列为什么需要 used 数组而不是像组合那样用一个 start 索引？因为排列的顺序是敏感的，[1,2,3] 和 [3,2,1] 是两个不同的解，每一层都必须从头开始扫所有候选数。组合则不需要考虑顺序，用 start 收缩候选区间就够了。区分这两者，基本就掌握了选择列表的设计方式。
4.2 第六题：组合总和
组合总和是回溯里最能体现剪枝价值的题。候选数组可以无限次使用同一个数，目标是找出所有和为 target 的组合。因为可以重复使用，所以递归进入下一层时，传入的不是 i+1 而是 i，表示当前数还能继续选。
我写完基础版之后，遇到了超时的问题。优化点分成两处：第一处是排序。先对 candidates 排序，然后在循环里加一个判断：如果 target - candidates[i] < 0，直接 break，而不是 continue。因为数组有序，后面的候选数更大，更不可能满足条件，可以一口气剪掉整个分支。这是“排序让剪枝成为可能”的典型例子。
第二处是重复组合的去重。组合总和的变体往往带着重复元素，比如 [2, 5, 2, 6]，如果不处理，会产生 [2,2,5] 和 [2,5,2] 这种重复。标准写法是在同一层循环里跳过重复值：
python复制def combinationSum2(candidates, target):
candidates.sort()
res = []
def backtrack(start, path, remain):
if remain == 0:
res.append(path[:])
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i - 1]:
continue
if candidates[i] > remain:
break
path.append(candidates[i])
backtrack(i + 1, path, remain - candidates[i])
path.pop()
backtrack(0, [], target)
return res
去重条件 i > start 非常关键。这个条件保证的是：同一层循环里，如果当前元素和上一个元素相同，就跳过。但是上一次递归里已经使用过的元素不受影响。如果去掉 i > start，直接写成 if candidates[i] == candidates[i-1]，会把跨层的合法重复也剪掉，导致漏解。我当时在这里卡了很长时间，直到画了递归树才看明白。
4.3 剪枝是回溯的灵魂
很多刚接触回溯的人以为模板写出来就结束了，其实模板只是地基，剪枝才是区分“能跑”和“能过”的分水岭。剪枝的本质是在递归树的某个节点处，提前判断这个分支是否可能存在解，不存在就整棵子树都砍掉。
剪枝有哪些常见手法？我整理了三个方向。第一，对结果排序后，一旦当前值已经不满足约束，后续值更大也不可能满足，使用 break 跳出循环。第二，同一层递归中，跳过值相同的元素，避免产生重复解。第三，记录“剩余目标值”而不是每次都重新计算，加减法之间的微小开销在大数据量下会被放大好多倍。
剪枝不是越狠越好，它有一个前提：必须是安全的，即剪掉的分支不可能包含合法解。排序后 break 是安全的，因为递增序列决定了后续值必然更大。跳过同层相同值也是安全的，因为这两个候选数产生的组合在结构上完全一致。但如果为了剪枝而改变了递归路径的语义，就会出大问题。我见过有同学用 if i > 0 而不是 if i > start 去重，结果把 [2, 2, 3] 这种本身合法的组合剪没了，原因就是跨层去重误伤了本应保留的分支。
4.4 调试回溯题的可视化方法
回溯题难debug，因为递归的调用栈和状态回退同时发生，靠print打点看不清楚。我后来学到一个方法：在进入递归和退出递归的地方分别打点，用缩进表示递归深度。
每次进入 backtrack 时打印当前路径和缩进，每次退出时打印“撤销后”的路径。这样能看到完整的调用树，每个节点的进入和退出都会成对出现，哪个分支没被回退一眼就看出来。打印效果类似下面这种格式：
code复制选择前 path=[1]
选择前 path=[1,2]
选择前 path=[1,2,3]
选择后 path=[1,2]
选择后 path=[1]
选择后 path=[]
如果发现某个选择后没有对应的选择前，说明递归返回时漏掉了 pop。这种问题看日志比盯代码快得多。我每次写回溯题，都会先把这个打印框架写好，AC之后再删掉。代码量没增加多少，但debug效率翻倍。
5. 六道题横向对比与套路沉淀
5.1 三种题型的适用场景对照表
刷完今天的题，我习惯把三类题放到一起做对比，找它们的异同。
| 题型 | 核心数据结构 | 典型标志词 | 复杂度模型 | 核心手法 |
|---|---|---|---|---|
| 双指针 | 数组、字符串 | 有序、原地、区间 | O(n) 或 O(n^2) 降到 O(n) | 快慢 / 左右 / 滑动 |
| 链表 | 单链表、双链表 | next、环、倒数第k个 | O(n), O(1) | 画图、哑节点、数学推导 |
| 回溯 | 递归树、选择列表 | 所有组合、所有排列、是否存在解 | 指数级 | 选择、撤销、剪枝 |
一个很大的感悟是：这三类题有一个共同的底层能力，叫做“状态维护”。双指针维护的是一段区间的边界，链表维护的是节点间的连接关系，回溯维护的是选择的集合。刷题刷到最后，其实都是在练这个能力，而不是在背具体的题。
5.2 从“会写代码”到“会讲题”
如果目标是面试，光会写还不够，还得会讲。我今天试着用“暴力 → 优化 → 边界”三段式把每道题讲了一遍。以三数之和为例：暴力就是三重循环，O(n^3)；优化是排序后用双指针把内层两重循环降成一层，O(n^2)；边界要注意排序后的数组可能重复，去重要分层处理。
这个方法听起来简单，实际上很考验对题目的理解深度。我记得第一次练习讲题的时候，讲到环形链表 II 的数学推导，一句话带过“快慢指针相遇后从头走就行”，结果面试官追问“为什么”，我当场愣住了。从那以后我强制自己把每个结论的推导过程写下来，今天那些推导就是这么攒出来的。
5.3 后续可以怎么扩展
这6道题刷完，我顺手给自己列了几个下周的扩展方向，都是今天题型的直接延伸：
- 双指针下一步刷滑动窗口，比如无重复字符的最长子串，和今天的快慢指针是同一个思维模型。
- 链表下一步刷LRU缓存，它是哈希表加双向链表的组合，能检验对指针操作的掌握程度。
- 回溯下一步刷解数独、N皇后，这两个题把剪枝用到极致，也能练习写“isValid”判断函数。
另外我打算把今天的6道题标成“重点回刷”，因为它们的价值不在AC本身，而在于背后的模板和推导。回刷的时候我会刻意不看代码，只靠思路复现，写不出来再看题解，这样印象最深。
我个人体会是，算法打卡最忌讳的是“刷完就忘”。今天本来想直接开新题，后来还是忍住了，把环形链表 II 的推导过程默写了一遍。事实证明这个决定是对的，因为写这篇总结的时候，我几乎不需要翻代码就能回忆起每一步的来龙去脉。建议你也试试：每周末挑一天，把本周刷过的题不参考任何资料重新写一遍，写不出来的那些，才是你真正需要复盘的题目。