2026-03-15，周日，算法打卡第23天。今天准备了一份“组合拳”题单：双指针、链表、回溯算法，三个专题共6道题。这6道题不是随便凑的，练完之后你会发现一个很有意思的事实——这三个看似独立的专题，底层的思维方式其实是一套东西：穷举所有的可能性，再用约束条件把没必要的分支砍掉。双指针是砍掉有序序列里的无效比较，链表操作是小心翼翼地改引用关系，回溯则是走迷宫式的“试一步、退一步”。
这套题单适合几类人：准备面试、想系统巩固基础算法、或者参加蓝桥杯这类比赛的人。难度上从简单到中等都有，不会上来就把人劝退，但也绝没有白给的题，每道题都有值得反复咀嚼的细节。这篇文章不只是给答案，我会把每一题的思考过程、关键代码、易错点全部拆开讲一遍。
1. 今日清单与训练思路
1.1 为什么把这三个专题放在同一天
我练算法有个习惯：同一类题连续刷容易产生路径依赖，今天做对了不代表真懂了，可能只是记住了套路。所以我会把关联度高的专题交叉着来，双指针、链表、回溯正好是三个经常在面试题里“串门”的考点。
双指针解决的是有序或区间类问题，核心是利用单调性减少枚举次数。链表是天然的指针操作练习场，练的是对引用赋值的精准控制。回溯算法则是暴力枚举的高级形态，它解决的是“在多个选择中搜索可行解”的问题。三个专题有一个共同点：都需要你在大脑里维护一个清晰的状态。
做个类比你就明白了。双指针像两个人站在一条线的两端，根据条件一点点靠近，谁该动、为什么动是解题关键。链表操作像在调整一列多米诺骨牌中间某几张的位置，动之前必须想清楚谁指向谁，顺序错了整条链就断了。回溯算法像在迷宫里走路，每条路都试一步，走不通就退回上一个岔路口换一条路。
这三个专题同一天练，等于把“维护状态、做出选择、撤销选择”这套思维模型练了三遍。后面做题你会发现，好多难题其实就是这几个基础模型的组合。
1.2 今日题目清单与难度对标
今天的6道题我按专题归类，也标了难度和核心考点，方便你对照练习：
| 题目 | 专题 | 难度 | 核心考点 | | 三数之和 | 双指针 | 中等 | 排序 + 左右指针夹逼 + 去重 | | 盛最多水的容器 | 双指针 | 中等 | 贪心移动矮边，证明移动正确性 | | 反转链表 | 链表 | 简单 | 迭代三指针 / 递归，指针保存顺序 | | 环形链表 II | 链表 | 中等 | 快慢指针 + 环入口的数学推导 | | 全排列 | 回溯 | 中等 | visited标记 + 递归 + 状态撤销 | | 组合总和 | 回溯 | 中等 | 排序剪枝 + startIndex控制 + 可重复取数 |
这个组合在面试中出现频率极高。三数之和是双指针的“招牌题”，盛水容器是同思路的变体；反转链表几乎是链表题的“开胃菜”，环形链表是快慢指针的进阶；全排列是回溯的入门必做，组合总和则加了排序剪枝的优化点。把这6道吃透，很多中等难度的题你都会感觉“见过”。
2. 双指针专题：左右夹逼与快慢推进
2.1 双指针的本质与两大范式
双指针听起来高大上，本质就是“在遍历过程中用两个下标代替一个下标，减少重复计算”。它分为两大类：一类是相向而行的左右指针，通常用在有序数组或者需要比较两个端点的场景；另一类是同向而行的快慢指针，通常用在链表中找特定位置或判断是否有环的场景。
左右指针的典型场景是：在一段有序的数组里找两个数，使得它们的和等于某个值。暴力做法是两层循环，时间复杂度O(n²)。但如果数组有序，你就可以用一个指针指最左，一个指最右，根据当前和的大小决定往哪边移动。为什么有序那么重要？因为有序给了你一个单调性，你知道左边小右边大，和偏大就动右边，和偏小就动左边，每次移动都距离目标更近一步。
快慢指针的典型场景是：判断链表有没有环。慢指针每次走一步，快指针每次走两步，如果链表有环，它们必然会在环里相遇。好比操场上两个人跑步，速度快的迟早套圈追上速度慢的。这两个范式对应到这周的三数之和、盛水容器、环形链表三题，你会发现核心其实就是一个移动规则的问题。
2.2 三数之和的排序与去重细节
三数之和要求在一个数组里找到所有三个数的组合，使得它们的和为0，并且结果不能包含重复三元组。很多人第一反应是三重循环，但题目要求去重，三重循环去重会写得非常痛苦，复杂度也不对。
正确做法是先排序，然后固定第一个数i，剩下两个数用左右指针在i后面这段区间里夹逼。排序的意义有两个：一来是方便我们用和的大小来移动指针，二来是让相同的数字聚在一起，方便去重。
这里最容易被坑的是去重的时机。我见过不少新手在收集到一组答案之后，直接用while跳过重复元素，这个没问题，但容易写得粗糙导致越界。更常见的问题是在第一层循环里忘掉跳过重复的i。记住一个口诀：外层i去重看nums[i]和nums[i-1]是否相等，内层left/right去重要在找到一组解之后再做。还有一个小优化：如果nums[i]本身已经大于0，因为数组升序，后面的数全都大于0，直接break掉，这是很自然的剪枝。
2.3 盛最多水的容器为什么移动矮边
这个题的经典场景是：给你一堆高度，每两个高度形成一条线段，线段之间围出一个矩形区域，矩形的宽是两个下标的距离，高是两条线段中较矮的那条，问能围出的最大面积是多少。
最直接的思路是双重循环枚举所有组合，O(n²)复杂度在数据量大的时候会超时。双指针的解法是从两端开始，每次计算当前面积，然后移动高度较小的那一端。很多人理解不了：为什么移动矮边一定不会漏掉最大值？
关键在于宽度。两个指针从两端出发，宽度是不断减小的。如果移动的是高边，宽度在缩小，新高度就算更高，但面积要取较矮的那条，最终高度不可能超过原来的矮边，所以面积一定比当前更小。反过来，如果移动矮边，虽然宽度减小了，但新的高度有可能会变大，面积才有可能超过当前值。这个贪心策略的正确性是可以用数学归纳严格证明的，但实际操作中你只要记住这一个判断：移动矮边才有面积变大的可能，移动高边完全没有可能。
我写这个题的时候会先算面积，再移动，不要提前移动指针导致面积算错。边界情况就是数组只有两个元素，这种情况直接返回唯一的面积即可。
3. 链表专题：遍历、反转与环检测
3.1 链表题的指针基本功
链表题让我总结一条最重要的经验：修改next之前，先把下一个节点保存下来。这句话看似简单，实际做题时最容易破功。反转链表里，如果你直接执行curr.next = prev，那原来curr后面的链表就找不到了，整条链表直接断掉。
链表节点就是一个对象，里面装着值和一个指向下一个节点的引用。操作链表本质就是操作引用。很多人搞不清链表头是谁、结尾怎么判断，建议画一张图，把每个节点画成格子，把next画成箭头，一步一步跟着代码走一遍，比眼睛盯着屏幕看十遍都有用。
另一个建议是学会使用哑节点。哑节点就是一个虚拟头节点，它本身的val没有任何意义，但因为它始终指向链表真正的头节点，很多边界情况就不用单独判断了。比如你需要在头部插入节点、删除头节点，或者链表可能为空，用哑节点可以省掉一堆if-else。
3.2 反转链表的两种写法对比
反转链表是链表题的老祖宗，几乎每次面试都可能遇到。迭代法用一个prev指针记录前驱，一个curr指针记录当前节点，在循环里先用临时变量保存curr.next，再把curr.next指向prev，然后整体前移。循环结束后，prev恰好是反转后的新头节点。
递归法的思路要难理解一些：先递归到链表的末尾，让最后一个节点成为新链表的头，然后在回溯的过程中把每个节点的next反过来指。核心就是head.next.next = head和head.next = None这两个赋值。很多人在这一步绕晕，是因为没想明白递归返回来的值是什么——返回值是已经反转好的链表的头节点，而不是当前节点。如果是第一次学递归，我建议先画递归栈，画出每一层的状态，很快就能理顺。
我个人的建议是面试优先写迭代法。迭代法空间复杂度O(1)，递归法虽然代码短，但空间复杂度O(n)，而且递归的调用栈深度在链表很长的时候有风险。如果面试官问递归写法，你再写出来也不迟。
3.3 环形链表 II 的数学推导
环形链表I是问有没有环，环形链表II要更进一步：返回入环的第一个节点。这题用快慢指针先找到相遇点，然后有一个经典的数学结论：一个指针从链表头出发，一个指针从相遇点出发，都每次走一步，它们最终会在入环点相遇。
这个结论很多人会背，但要真正理解才有底气。假设链表头到入环点的距离是a，入环点到相遇点的距离是b，相遇点继续走到入环点的距离是c。慢指针走了a+b步，快指针走了a+b+c+b步。因为快指针速度是慢指针的两倍，所以2(a+b) = a+b+c+b，化简得到a = c。这意味着从链表头到入环点的距离，恰好等于从相遇点继续走到入环点的距离。所以两个指针同速走，必然同时到达入环点。
实现上要注意：快指针走两步之前要先判断fast和fast.next都不为空，否则会空指针异常。还要记得，如果循环结束都没有相遇，说明没有环，返回None。
4. 回溯算法：模板、剪枝与去重
4.1 回溯本质：状态树上的DFS
回溯算法本质是一种深度优先搜索，它的核心操作就是三个步骤：做选择、递归、撤销选择。很多人觉得回溯难，是因为没有把它的状态变化想清楚，程序在递归中一层层往下走，每层都是一个独立的岔路口，撤销选择是为了让程序能回到上一层继续探索其他分支。
我用一个生活化的例子来解释。你在一个陌生的公园里找出口，每个岔路口都试一条路往前走，走了一段发现是死路，就沿原路退回岔路口，再试另一条路。回溯算法里的递归调用就是往前走，return就是碰到死路，把刚才的选择撤销掉就是回到岔路口。
回溯题的状态空间是一个树形结构。树的每一层代表递归的深度，树的每一个分支就是一种可能的选择。解题的关键是剪枝——在递归过程中尽早地判断某些分支不可能产生合法解，直接跳过。剪枝做得好，程序可能从几亿次递归降到几千次，这也是为什么很多回溯题都要求先排序。
4.2 全排列和组合的差别在哪里
全排列和组合都是经典回溯，但细节差异非常重要。全排列关注顺序，[1,2]和[2,1]是两个不同的排列，所以在每一层递归都要遍历所有节点，靠一个used数组来标记哪些数字已经被选过，避免重复取同一个数字。
组合题目不关注顺序，[1,2]和[2,1]是同一个组合，所以不能让后面的元素再和前面的元素组合一遍，否则就会大量重复。处理方式是用一个startIndex参数，告诉当前递归从哪个位置开始取数，这样就能保证组合中元素的相对顺序是递增的，天然去重。
如果原数组里还有重复元素，那就要再加一层去重逻辑：先排序，然后在同一层递归里，如果当前元素和前一个元素相同，并且前一个元素还没被使用过，就跳过。这个逻辑很容易写错，常见错误是把“前一个元素被使用过”和“前一个元素没被使用过”的条件搞反了。核心思想是保证在同一个树层不重复用相同的值，而在同一条树枝上允许连续使用相同值。
4.3 组合总和的排序剪枝思路
组合总和这个题，candidates里的数可以无限次重复使用，目标是从中选出一组数使其和等于target。这里有两个处理要点：一是递归下一层时的起点，传i而不是i+1，因为当前数字可以重复使用；二是排序之后可以提前break，因为数组已经升序，一旦当前数字比剩余目标值还大，后面的数字也一定更大，整个循环都可以结束。
举一个实际例子，candidates为[2,3,6,7]，target为7。从2开始，2可以用多次，路径是2-2-3，和为7，记录答案；然后是2-3，还剩2，再取3就超过了，break；然后换分支。如果你不排序，在递归里面对大于剩余目标值的数字就不能用break，只能continue，也是对的，但效率差不少。
我写回溯的代码时有一个习惯：在递归函数开头打印当前状态，比如path和remain的值。这个小技巧在调试时特别管用，能直观看到搜索的路径和剪枝点。
5. 六道题逐一拆解与代码复盘
5.1 三数之和：先排序，再夹逼
三数之和的完整代码我习惯这样写：
def threeSum(nums): nums.sort() n = len(nums) res = [] for i in range(n - 2): if nums[i] > 0: break 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: left += 1 elif total > 0: right -= 1 else: res.append([nums[i], nums[left], nums[right]]) while left < right and nums[left] == nums[left + 1]: left += 1 while left < right and nums[right] == nums[right - 1]: right -= 1 left += 1 right -= 1 return res这部分有两个地方容易写错。第一个是外层去重必须写成nums[i] == nums[i - 1]，不能写成nums[i] == nums[i + 1]，否则会漏掉解。第二个是找到一组解后，去重要放在记录答案之后，否则可能把本来合法的组合跳过。
我上个月用这个题帮朋友做模拟面试，她的错误就是去重时机不对，用了i+1去重，结果[ -1, -1, 2 ]这种解直接被漏掉了。所以记住：外层i去重总跟前面比，找到答案后内层指针再用while跳过重复值。
5.2 盛最多水的容器：每次移动矮边
代码很简单，核心逻辑只有几行：
def maxArea(height): left, right = 0, len(height) - 1 ans = 0 while left < right: area = min(height[left], height[right]) * (right - left) ans = max(ans, area) if height[left] < height[right]: left += 1 else: right -= 1 return ans写这个代码的时候，我习惯把left和right命名为i和j，这样在脑海里更容易对应到公式里的下标。面积计算用的是当前两边高度的较小值，乘以宽度。移动哪一边的依据就是比较两边的高度，哪个矮就移动哪个。如果高度相等，移动哪边都可以，任意选一个更简单的方向。
这个题的难点不在代码，而在证明这样移动不会错过最优解。面试时能画出证明过程，会比直接背代码加分不少。我的记忆方法就是一句话：“宽度一直在缩小，只有提高矮边才有机会得到更大面积。”
5.3 反转链表：迭代和递归的对比
迭代版：
def reverseList(head): prev = None curr = head while curr: temp = curr.next curr.next = prev prev = curr curr = temp return prev递归版：
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迭代版的核心就是先用temp把后面的链条存住，再改当前指针指向prev。我见过好几个同学把这行temp = curr.next漏掉，导致链表断掉，一调试就是空指针，特别浪费时间。
递归版的理解建议用一层具体例子推：假设head是1，head.next是2，2的next是3。reverseList(2)返回以3为头、方向反转后的新链表。这时候2.next还是3，所以head.next.next = head就是把3的next指向1，1的next设为None。递归的本质就是把“当前节点后面的链表先反转好”，再把当前节点接上去。
5.4 环形链表 II：快慢指针找入口
def detectCycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: slow = head while slow != fast: slow = slow.next fast = fast.next return slow return None这里的重点在于第一阶段的快慢指针不能跳过相遇。如果链表很长，环很大，快慢指针会在环内转圈，但一定能相遇。第二阶段，slow从链表头出发，fast从第一次相遇点出发，同速向前，两者相遇的位置就是入环点。
这个题我建议你亲手推一遍数学公式再上机，直接背代码容易在面试里被追问推导过程。推导结果就是a = c，这个等式也是整个算法的灵魂。
5.5 全排列：used标记当前路径
def permute(nums): res = [] used = [False] * len(nums) path = [] def dfs(): 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]) dfs() path.pop() used[i] = False dfs() return res两个关键点：第一，收集结果时一定要用path[:]拷贝，直接append(path)的话，后面pop操作会把已经存进去的路径一起改掉。第二，递归进入下一层时，遍历起点是0而不是startIndex，因为排列里顺序不同结果不同，每个元素都可能出现在任意位置。
5.6 组合总和：可重复取数 + 剪枝
def combinationSum(candidates, target): res = [] candidates.sort() path = [] def dfs(start, remain): if remain == 0: res.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] > remain: break path.append(candidates[i]) dfs(i, remain - candidates[i]) path.pop() dfs(0, target) return res这个题最关键的代码是dfs(i, remain - candidates[i])，传的是i不是i+1，表示当前数字取完之后还能再取。排序后再加一个if candidates[i] > remain: break，这就是剪枝。注意是break而不是continue，因为排序后后面的数更大，全部不合格。
有些变体会把条件改成每个数字只能用一次，那就把dfs(i, ...)改成dfs(i + 1, ...)，同时再对同一层重复值做跳过处理。建议你把这两个版本的差距亲手敲一遍，感受一下这几行变化的影响力。
6. 排坑实录与刷题建议
6.1 高频易错点速查表
我把今天6道题里容易踩的坑整理成一个表格，这些基本都是我自己或身边同学真正犯过的错误：
| 专题 | 易错场景 | 正确做法 | | 双指针 | 三数之和外层去重写成与后一个比较 | 应与前一个nums[i-1]比较 | | 双指针 | 盛水容器先移动指针再算面积 | 必须先算面积，后移动 | | 链表 | 反转链表忘记保存下一个节点 | 用temp = curr.next提前保存 | | 链表 | 环形链表的循环条件写成while fast.next | 必须同时判断fast和fast.next不为空 | | 回溯 | 收集结果直接用res.append(path) | 必须用path[:]创建副本 | | 回溯 | 组合总和递归下一层传i+1 | 可重复取数时传i，不可重复传i+1 |
这个表格建议你保存下来，每次做同类题之前看一眼，能省很多调试时间。
6.2 实际调试中的体会与习惯
我今天做这6道题，每道都刻意跑了一遍极端用例。三数之和我试了全0数组，结果应该是[[0,0,0]]，这个用例能验证去重逻辑是否正确。盛水容器我用高度单调递增的数组验证每一步移动都没有漏掉最大值。反转链表我专门试了只有一个节点的链表，确保返回的prev确实是原节点而不是None。环形链表II我构造了一个头节点就在环里的链表，这种情况第二阶段循环一次都不执行，直接返回的就是头节点。
调试链表题最有效的方法还是画图。我用白板把反转链表的前两步画出来，每个节点一个方框，next是箭头，然后拿手指头跟着代码走一遍，比在内存里反复打印next值直观得多。回溯题调试我用的是打印递归参数的方法，这就像给迷宫探险者一路留下走过的痕迹，回头排查时非常清楚。
最后分享一个我做回溯题的小习惯。每写一个回溯函数，我都先定义好它的参数语义再动笔。比如全排列里的dfs()不传任何参数，因为路径信息都在path和used里；组合总和里的dfs(start, remain)负责告诉递归“你现在可以从哪个位置开始、目标还剩多少”。参数越少，越不容易混乱，但该有状态的也不要省。很多复杂度高的回溯题，错误都发生在参数语义不清上。这个经验在你后面做子集、N皇后这类题时会非常受用。
