1. 从一道中等题说起为什么“孪生和”值得单独写一篇力扣的链表题里2130题“链表最大孪生和”绝对是被低估的那种题目。它看起来只是一个求最大值的问题但真正动手做会发现这道题把链表遍历、快慢指针、反转链表、空间复杂度优化全串在了一起。我刷了这么多链表题敢说这道题是检验链表基本功是否扎实的绝佳试金石。题目本身不复杂给一个长度为偶数的单链表把第 i 个节点和第 n-1-i 个节点配成一对孪生节点求所有孪生节点值之和的最大值。比如链表是 1-2-3-4那么(1,4)的和是5(2,3)的和也是5答案就是5。说它被低估是因为很多刷题的人一看“求最大值”就条件反射想用数组或暴力但题目真正想考察的是你能不能在不复制数组的前提下用链表自身的操作完成这件事。这也是面试官最爱问的点——你的解法空间复杂度是O(n)还是O(1)这决定了这道题你是“做出来了”还是“做好了”。这篇文章我会从暴力思路讲起再到最优解把每一步为什么这么想、怎么写最稳、坑在哪全部拆开讲。无论你是刚接触链表的新手还是刷题到了中期想巩固基础的选手这篇文章都能给你一些实在的东西。2. 题目拆解先理解孪生和到底在求什么2.1 双向奔赴的节点配对孪生节点的定义是题目里最核心的信息。当链表长度为 n 时第 i 个节点从0开始数和第 n-1-i 个节点是一对。这个配对方式有一个很有意思的特性它是对称的像一根绳子从两端往中间折。拿 [1,2,3,4,5,6] 举例第0个节点1和第5个节点6配对和是7第1个节点2和第4个节点5配对和是7第2个节点3和第3个节点4配对和也是7你会发现这个链表的所有孪生和都一样但题目没说所有链表都这么规律。比如 [4,2,2,3] 里第0个节点4和第3个节点3配对和是7第1个节点2和第2个节点2配对和是4最大孪生和就是7。这个例子的意义在于提醒我们配对是固定的不是随便找两个节点加一起就行。我第一次做的时候差点想成“求最大两个节点之和”结果配对规则一对不上答案就错这是最容易踩的坑。2.2 为什么链表长度必须是偶数题目明确了链表长度是偶数这不是随便说说的。因为 n 必须是偶数才能保证每个节点都有且只有一个孪生节点。如果 n 是奇数中间那个节点就找不到对称的伙伴了配对规则就崩了。这个条件其实是在降低题目难度。你想如果长度可以是奇数你还得额外处理中间节点怎么办但我们不需要考虑这种边角情况。不过在实际面试中建议你要主动提一句“题目保证了偶数长度但如果奇数的话我就需要单独定义处理规则。”这会让面试官觉得你考虑问题比较周到。2.3 暴力解法最朴素的两种思路先别急着写快慢指针和反转链表暴力思路虽然面试不会让你这么答但它能帮你彻底理解题目。最简单的思路第一步遍历链表把值全部存到数组里第二步用双指针从数组两端往中间扫每扫到一对就算一次和更新最大值。这个思路时间复杂度O(n)空间复杂度O(n)代码简单到不能再简单class Solution: def pairSum(self, head: Optional[ListNode]) - int: vals [] while head: vals.append(head.val) head head.next ans 0 i, j 0, len(vals) - 1 while i j: ans max(ans, vals[i] vals[j]) i 1 j - 1 return ans这代码能过笔试拿分没问题但这不是这道题想教你的东西。数组解法把链表“降维”成了线性表完全绕过了链表的特性。就好比你明明在一家日料店却非要吃汉堡——能吃但没吃到店的精髓。另一种暴力思路是固定第 i 个节点每次从头遍历到第 n-1-i 个节点求和。这个思路的时间复杂度是O(n^2)明显太拉了刷题时没有任何场景值得用这条路纯属为了理解配对规则而存在。2.4 从暴力到最优优化的两个方向暴力解法的本质问题一是要额外空间存数组二是没有利用链表的结构优势。优化的方向其实就两条能不能不用额外数组能不能少跑几遍链表标准答案刚好把这两条都占了用快慢指针找到链表中点把后半段反转然后从两端同时遍历。整个过程的空间复杂度降到O(1)时间复杂度仍然是O(n)而且遍历次数是常数级别的。这个思路就是接下来要重点讲的。3. 最优解法核心快慢指针找中点 反转后半段3.1 三步走从读题到码代码的完整链路整个最优解法可以拆成三个阶段每一阶段都有它存在的必然理由。第一阶段“找中点”。因为孪生对的另一端是从尾部倒着数的所以想让两个节点同时被访问必须先把后半段“调个头”。调头之前得先确认从哪开始调这就是找中点的意义。第二阶段“反转后半段”。反转之后原来链表的结构就变成head 指向前半段第一个节点后半段反转后的头节点指向原链表的最后一个节点。这两个头我们分别记作 first 和 second分别往后走一步就能遍历到每一对孪生节点。第三阶段“同步遍历求和”。这是最简单的一步first 和 second 同时后移循环次数刚好是 n/2每次把两个节点的值相加更新答案就行。光看这三步可能觉得很简单但每一步的实现细节都能藏坑。下面我逐个展开。3.2 快慢指针找中点的原理与实现快慢指针是链表操作里的经典套路。慢指针 slow 每次走一步快指针 fast 每次走两步当 fast 到达链表末尾时slow 刚好在中点。这里的“中点”对于偶数长度链表来说恰好是右半段的第一个节点。为什么它俩能在中点相遇逻辑也很直白假设链表长度是 n快指针走的路程是慢指针的两倍当快指针走完 n 步到达末尾时慢指针走了 n/2 步也就是链表的中点位置。需要注意的细节是循环条件怎么写。通常有两种写法while fast and fast.nextwhile fast.next and fast.next.next以偶数长度为例比如链表长度是4slow 在节点1fast 在节点1走一步后 slow 到节点2fast 到节点3再走一步前判断条件fast 在节点3fast.next 是节点4不为空所以再走一步slow 到节点3fast 到节点5空。此时 slow 指向节点3正好是右半段的开始节点。C代码实现如下ListNode* slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; }需要注意的是如果你希望 slow 停留的位置是左半段的最后一个节点代码要微调成先判断 fast-next-next 是否为空。两种定位对应不同的后续处理方式我在第三部分会再详细对比。3.3 反转链表的标准模板与断链陷阱链表反转是必须写到肌肉记忆里的操作它的迭代写法我记了无数遍ListNode* prev nullptr; while (head) { ListNode* next head-next; head-next prev; prev head; head next; }这个模板看起来简单但反转后有一个极容易踩的坑反转完的后半段它的尾节点指针必须指向 nullptr否则遍历时会死循环。上面的模板每次循环都把当前节点的 next 指向 prev当处理完最后一个节点时它的 next 确实变成了 nullptr所以是安全结束的。另一个细节是反转的起点。我们在找中点时得到的是右半段第一个节点 slow如果直接从 slow 开始反转那么原链表的左半段还挂着 right 之前的节点即左半段最后一个节点的 next 仍然指向 slow而后半段反转后 slow 会变成尾节点它的 next 将被置为 nullptr。这时候左半段不受影响吗其实是受影响的因为左半段最后一个节点的 next 仍然指向那个“位置”只是那个位置现在变成了一个独立的链表。我们需要两个指针 first 和 second 来同时遍历所以人为地让 first 从头走second 从反转后的新头走互不干扰。由于 first 遍历的是前 n/2 个节点second 遍历的是后 n/2 个节点两边都不会走到对方的地盘上去所以中间的连接断不断其实无所谓。更严谨的做法是提前把左半段最后一个节点的 next 置为 nullptr这样可以避免潜在的问题代码看起来也更干净。做法是在找中点时让一个指针始终记录 slow 的前一个节点找到中点后前一个节点的 next 置空。我之前写的时候偷懒没断链结果代码也能跑因为遍历次数刚好只有 n/2不会越界。但后来发现如果面试官追问“你这两段链表之间还有什么关联”解释起来反而麻烦。主动断链是个更体面的写法。3.4 两种中点的定位方式以及怎么选找中点的时候有人喜欢让 slow 停在右半段第一个节点有人喜欢停在左半段最后一个节点。这两者的核心差异在于反转时从哪个节点开始。方式Aslow 停在右半段第一个节点。也就是前面代码 while(fast fast-next) 跑完后的状态。这种方式代码最简洁因为你直接拿 slow 当第二段的头开始反转就行。方式Bslow 停在左半段最后一个节点。用 while(fast-next fast-next-next) 作为循环条件。找到后slow-next 是右半段第一个节点从 slow-next 开始反转。这时你可以顺手 slow-next nullptr 做断链。我个人的建议是刷题时用方式A就够了思路少容易手稳但如果你想追求代码的“可解释性”方式B更清晰。两种方式我都贴一遍这样大家在不同场景可以选自己习惯的。3.5 双指针同步遍历最后的临门一脚反转完成后我们有了两个链表的头指针first原链表的 head和 second反转后链表的头。现在相当于有两条独立的链表我们要做的就是把 first 和 second 同步往前走一节节地配对求和。循环条件很简单while(second) 或者 while(first)。因为两个链表的长度都是 n/2所以用哪个判断都可以。这里有个细节如果用 second 作为循环条件那么反转后第二段链表的尾节点的 next 恰好是 nullptr循环结束时 second 也是 nullptr完美退出。C完整实现看这里int pairSum(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } ListNode* prev nullptr; while (slow) { ListNode* next slow-next; slow-next prev; prev slow; slow next; } ListNode* first head; ListNode* second prev; int ans 0; while (second) { ans max(ans, first-val second-val); first first-next; second second-next; } return ans; }这段代码以方式A为基准简洁清楚时间复杂度O(n)空间复杂度O(1)已经是这道题的最优解。4. 实操记录完整题解路线图和易错点排查4.1 写代码前先画一遍链表状态图很多人在白板上写链表题容易翻车原因在于对指针的指向变化没有直观认识。我在动手敲代码之前一定会先在草稿纸上画一遍链表状态变化尤其是找中点。拿一个长度为6的链表举例1-2-3-4-5-6。两条直线分别代表 first 和 fast。fast 每次跳两个节点slow 每次走一个节点。跑完后 slow 在4fast 在空。这时右半段就是 4-5-6反转后变成 6-5-4。动手画一次你会发现first 从头出发时1和6对应2和5对应3和4对应。三组配对全部被我们覆盖了没有露网之鱼。这个认知感一旦建立代码只是背书而已。4.2 常见错误空指针、漏循环、断错链链表题的错误大多是空指针访问。这道题常见的翻车点有三个。第一个是快慢指针循环结束条件写错。比如 while(fast-next fast-next-next)如果链表只有两个节点fast 初始在 headfast-next 不为空fast-next-next 为空循环不进slow 保持在 head此时 slow 停在左半段最后一个节点。这个行为是符合预期的但如果你本意是想让 slow 停在右半段第一个节点那就错了。所以循环条件必须和你的定位意图匹配。第二个是反转后忘记第二段链表的头是 prev 还是 slow。很多人第一次写反转会被最后的指针状态搞晕。在反转模板中循环结束后 prev 指向原链表的最后一个节点也是反转后的新头。所以遍历时应该用 prev 而不是 slow因为 slow 在循环结束时已经是 nullptr 了这是低级错误里最高发的一个。第三个是同步遍历时用了错误的循环次数比如 while(first-next) 或者 while(first-next second-next)。这里的 n/2 次遍历用 while(second) 最稳因为 second 链表的尾部天然是 nullptr不需要额外计数。如果你用的是 while(first)也以 nullptr 为边界同样没问题。最忌讳的是用“n/2”这种需要额外计数的方式因为链表的长度需要先遍历一遍才知道凭空多了一次 O(n)没有意义。4.3 内存问题C 解法务必手动管理好节点C 刷题虽然力扣环境会统一回收内存但如果你把代码拿到本地或者面试环境去跑反转后的链表已经和原链表共享了一部分节点对象你要格外小心二次释放的问题。比如原链表的所有节点如果由一个容器统一管理反转只是改动了 next 指针并没有新增节点。所以程序最后只需要释放从头节点开始的那一条链即可。但断链操作会让这条链少了一部分剩下那部分如果没人管就会内存泄漏。这就引出我前面说的建议不追求极端的话用方式A不主动断链反而更省心因为原链表的所有节点仍然在一条链上回收也方便。但如果你用了方式B主动断链记得要分别释放两段链表的所有节点。很多题解不会谈这一点因为 LeetCode 环境不检查内存泄漏但实际工程里这就是隐患。我写嵌入式链表代码时被内存问题坑过不少次所以这个点我在刷题时就特别留意。4.4 边界条件测试清单每次写完链表题我都会拿几个特殊数组测一下长度为2的最小链表长度为4所有值相同的链表长度为6前半段全小值、后半段全大值的链表节点值为负数的情况为什么要测负数因为如果初始答案设为 0而所有值都是负数正确结果应该是负数你用 0 初始化就错了。最佳实践是用 INT_MIN 或者让答案等于第一组孪生和之后再逐步更新。这个细节在力扣这类题目里其实不太重要因为题目给的取值范围包含了正数但面试时能提一句“我用 INT_MIN 初始化避免全负数的情况”会显得你工程素养不错。长度为2的链表是个特别容易出问题的测试快慢指针在 while(fast fast-next) 条件下fast 第一步到了空slow 到了第二个节点。反转后second 指向第二个节点first 还是第一个节点循环走一次就结束答案就是两个节点之和。逻辑完全正确。4.5 复杂度分析为什么说这个解法是最优时间复杂度方面找中点跑了一遍链表O(n)反转后半段也跑了半条链O(n/2)同步遍历又跑了半条链O(n/2)。所以总时间复杂度是 O(n)。空间复杂度方面整个求解过程只用了常数个指针变量没有额外数组没有递归所以是 O(1)。你可能想既然转数组也是 O(n)为什么非要用 O(1) 空间这里有两个层面的回答。第一个层面是“面试表现”面试官看到你用 O(1) 空间解出来会认为你对链表的操作足够熟悉而不是只会依赖数组。第二个层面是“实际工程的价值”在内存受限的嵌入式环境或者处理超大链表时O(n) 的额外空间可能就是不可接受的。这道题能帮你把反转链表和快慢指针这两个高频技巧一次练到位性价比极高。5. 衍生思考这道题背后的链表基本功池5.1 从孪生和到回文链表的迁移做完这道题你会发现它的解题路径和“回文链表”惊人地相似。判断一个链表是不是回文经典做法也是找中点、反转后半段、然后两端同步比较。区别仅仅是回文链表比较的是值是否相等孪生和求的是相加的最大值。这个迁移很有价值。因为面试官在考链表的时候非常爱出回文链表如果你已经彻底掌握了2130题回文链表就是换个判断条件而已。我还建议你顺便想一想如果要求每对孪生节点求和之后再求这些和的中位数该怎么做这就变成“找中点反转收集到数组排序”的综合题了刷题广度就是这样一点点扩开的。5.2 如果链表不是单链表而是双向链表呢双向链表做这道题会简单很多因为 tail 能直接往前找前任节点本质上不用反转。你能从“从尾部往前指”这个思路反推为什么单链表需要反转——就是因为单链表只有 next 指针没有 prev没法从后往前走。理解了这一点你就理解了反转是“绕路模拟双链表”的本质。在面试现场说清楚这个逻辑比背模板更有说服力。5.3 从链表操作到工程项目嵌入式场景怎么用链表不只是刷题用的抽象结构实际工程中链表的操作模式在嵌入式内核、内存管理、缓存淘汰策略里都非常常见。比如 LRU 缓存的核心操作就是把节点从链表中间摘下来放到头部这需要“找前驱”和“重接指针”和反转链表时的指针重连是同一套功夫。我举一个具体场景嵌入式系统里常用空闲链表来管理内存块操作系统分配内存时就要遍历这个链表找到合适大小的块并摘下来归还内存时又要把块插回链表的对应位置。这些操作和力扣里的插入删除没有任何本质区别只是代码风格更工程化多了很多条件判断和错误处理。所以我刷链表题的时候从来不是刷完就扔而是每次都在想“这套指针操作放到我的嵌入式代码里怎么改”。6. 总结我的实操心得刷这道题的正确姿势如果你正在准备面试或者想在链表专题上打好底子我建议你用下面的顺序来完成这道题。第一遍先用数组法做一遍确保你理解了孪生配对到底怎么配对。第二遍尝试自己推导出快慢指针加反转的思路不要一开始就看题解。如果你能独立把这个思路想出来说明你对链表操作已经有感觉了。第三遍把代码写完分别测长度为2、4、6的链表以及全负数节点值。第四遍尝试把代码改写成方式B断链版本理解两种实现之间的差异。我只说一遍别走马观花这道题练熟之后我敢说链表中点、链表反转、双指针遍历这三个专题你都能过关。很多人在力扣刷题刷到后面发现自己一直在做会的题这是最无效的刷题方式。像这种一道题能顶上三道题的知识密度的题目才是真正值得反复琢磨的。根据我个人的经验链表反转这个操作看似简单但每次隔一段时间不写重新上手总会有一瞬间的卡壳。所以我的建议是不要只看题解一定要自己亲手画一遍链表状态变化图亲手写一遍每个指针的移动过程。这样才能把模板变成你肌肉记忆里的一部分面试手撕代码时才不会慌乱。 链表最大孪生和：快慢指针+反转链表的最优解解析
1. 从一道中等题说起为什么“孪生和”值得单独写一篇力扣的链表题里2130题“链表最大孪生和”绝对是被低估的那种题目。它看起来只是一个求最大值的问题但真正动手做会发现这道题把链表遍历、快慢指针、反转链表、空间复杂度优化全串在了一起。我刷了这么多链表题敢说这道题是检验链表基本功是否扎实的绝佳试金石。题目本身不复杂给一个长度为偶数的单链表把第 i 个节点和第 n-1-i 个节点配成一对孪生节点求所有孪生节点值之和的最大值。比如链表是 1-2-3-4那么(1,4)的和是5(2,3)的和也是5答案就是5。说它被低估是因为很多刷题的人一看“求最大值”就条件反射想用数组或暴力但题目真正想考察的是你能不能在不复制数组的前提下用链表自身的操作完成这件事。这也是面试官最爱问的点——你的解法空间复杂度是O(n)还是O(1)这决定了这道题你是“做出来了”还是“做好了”。这篇文章我会从暴力思路讲起再到最优解把每一步为什么这么想、怎么写最稳、坑在哪全部拆开讲。无论你是刚接触链表的新手还是刷题到了中期想巩固基础的选手这篇文章都能给你一些实在的东西。2. 题目拆解先理解孪生和到底在求什么2.1 双向奔赴的节点配对孪生节点的定义是题目里最核心的信息。当链表长度为 n 时第 i 个节点从0开始数和第 n-1-i 个节点是一对。这个配对方式有一个很有意思的特性它是对称的像一根绳子从两端往中间折。拿 [1,2,3,4,5,6] 举例第0个节点1和第5个节点6配对和是7第1个节点2和第4个节点5配对和是7第2个节点3和第3个节点4配对和也是7你会发现这个链表的所有孪生和都一样但题目没说所有链表都这么规律。比如 [4,2,2,3] 里第0个节点4和第3个节点3配对和是7第1个节点2和第2个节点2配对和是4最大孪生和就是7。这个例子的意义在于提醒我们配对是固定的不是随便找两个节点加一起就行。我第一次做的时候差点想成“求最大两个节点之和”结果配对规则一对不上答案就错这是最容易踩的坑。2.2 为什么链表长度必须是偶数题目明确了链表长度是偶数这不是随便说说的。因为 n 必须是偶数才能保证每个节点都有且只有一个孪生节点。如果 n 是奇数中间那个节点就找不到对称的伙伴了配对规则就崩了。这个条件其实是在降低题目难度。你想如果长度可以是奇数你还得额外处理中间节点怎么办但我们不需要考虑这种边角情况。不过在实际面试中建议你要主动提一句“题目保证了偶数长度但如果奇数的话我就需要单独定义处理规则。”这会让面试官觉得你考虑问题比较周到。2.3 暴力解法最朴素的两种思路先别急着写快慢指针和反转链表暴力思路虽然面试不会让你这么答但它能帮你彻底理解题目。最简单的思路第一步遍历链表把值全部存到数组里第二步用双指针从数组两端往中间扫每扫到一对就算一次和更新最大值。这个思路时间复杂度O(n)空间复杂度O(n)代码简单到不能再简单class Solution: def pairSum(self, head: Optional[ListNode]) - int: vals [] while head: vals.append(head.val) head head.next ans 0 i, j 0, len(vals) - 1 while i j: ans max(ans, vals[i] vals[j]) i 1 j - 1 return ans这代码能过笔试拿分没问题但这不是这道题想教你的东西。数组解法把链表“降维”成了线性表完全绕过了链表的特性。就好比你明明在一家日料店却非要吃汉堡——能吃但没吃到店的精髓。另一种暴力思路是固定第 i 个节点每次从头遍历到第 n-1-i 个节点求和。这个思路的时间复杂度是O(n^2)明显太拉了刷题时没有任何场景值得用这条路纯属为了理解配对规则而存在。2.4 从暴力到最优优化的两个方向暴力解法的本质问题一是要额外空间存数组二是没有利用链表的结构优势。优化的方向其实就两条能不能不用额外数组能不能少跑几遍链表标准答案刚好把这两条都占了用快慢指针找到链表中点把后半段反转然后从两端同时遍历。整个过程的空间复杂度降到O(1)时间复杂度仍然是O(n)而且遍历次数是常数级别的。这个思路就是接下来要重点讲的。3. 最优解法核心快慢指针找中点 反转后半段3.1 三步走从读题到码代码的完整链路整个最优解法可以拆成三个阶段每一阶段都有它存在的必然理由。第一阶段“找中点”。因为孪生对的另一端是从尾部倒着数的所以想让两个节点同时被访问必须先把后半段“调个头”。调头之前得先确认从哪开始调这就是找中点的意义。第二阶段“反转后半段”。反转之后原来链表的结构就变成head 指向前半段第一个节点后半段反转后的头节点指向原链表的最后一个节点。这两个头我们分别记作 first 和 second分别往后走一步就能遍历到每一对孪生节点。第三阶段“同步遍历求和”。这是最简单的一步first 和 second 同时后移循环次数刚好是 n/2每次把两个节点的值相加更新答案就行。光看这三步可能觉得很简单但每一步的实现细节都能藏坑。下面我逐个展开。3.2 快慢指针找中点的原理与实现快慢指针是链表操作里的经典套路。慢指针 slow 每次走一步快指针 fast 每次走两步当 fast 到达链表末尾时slow 刚好在中点。这里的“中点”对于偶数长度链表来说恰好是右半段的第一个节点。为什么它俩能在中点相遇逻辑也很直白假设链表长度是 n快指针走的路程是慢指针的两倍当快指针走完 n 步到达末尾时慢指针走了 n/2 步也就是链表的中点位置。需要注意的细节是循环条件怎么写。通常有两种写法while fast and fast.nextwhile fast.next and fast.next.next以偶数长度为例比如链表长度是4slow 在节点1fast 在节点1走一步后 slow 到节点2fast 到节点3再走一步前判断条件fast 在节点3fast.next 是节点4不为空所以再走一步slow 到节点3fast 到节点5空。此时 slow 指向节点3正好是右半段的开始节点。C代码实现如下ListNode* slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; }需要注意的是如果你希望 slow 停留的位置是左半段的最后一个节点代码要微调成先判断 fast-next-next 是否为空。两种定位对应不同的后续处理方式我在第三部分会再详细对比。3.3 反转链表的标准模板与断链陷阱链表反转是必须写到肌肉记忆里的操作它的迭代写法我记了无数遍ListNode* prev nullptr; while (head) { ListNode* next head-next; head-next prev; prev head; head next; }这个模板看起来简单但反转后有一个极容易踩的坑反转完的后半段它的尾节点指针必须指向 nullptr否则遍历时会死循环。上面的模板每次循环都把当前节点的 next 指向 prev当处理完最后一个节点时它的 next 确实变成了 nullptr所以是安全结束的。另一个细节是反转的起点。我们在找中点时得到的是右半段第一个节点 slow如果直接从 slow 开始反转那么原链表的左半段还挂着 right 之前的节点即左半段最后一个节点的 next 仍然指向 slow而后半段反转后 slow 会变成尾节点它的 next 将被置为 nullptr。这时候左半段不受影响吗其实是受影响的因为左半段最后一个节点的 next 仍然指向那个“位置”只是那个位置现在变成了一个独立的链表。我们需要两个指针 first 和 second 来同时遍历所以人为地让 first 从头走second 从反转后的新头走互不干扰。由于 first 遍历的是前 n/2 个节点second 遍历的是后 n/2 个节点两边都不会走到对方的地盘上去所以中间的连接断不断其实无所谓。更严谨的做法是提前把左半段最后一个节点的 next 置为 nullptr这样可以避免潜在的问题代码看起来也更干净。做法是在找中点时让一个指针始终记录 slow 的前一个节点找到中点后前一个节点的 next 置空。我之前写的时候偷懒没断链结果代码也能跑因为遍历次数刚好只有 n/2不会越界。但后来发现如果面试官追问“你这两段链表之间还有什么关联”解释起来反而麻烦。主动断链是个更体面的写法。3.4 两种中点的定位方式以及怎么选找中点的时候有人喜欢让 slow 停在右半段第一个节点有人喜欢停在左半段最后一个节点。这两者的核心差异在于反转时从哪个节点开始。方式Aslow 停在右半段第一个节点。也就是前面代码 while(fast fast-next) 跑完后的状态。这种方式代码最简洁因为你直接拿 slow 当第二段的头开始反转就行。方式Bslow 停在左半段最后一个节点。用 while(fast-next fast-next-next) 作为循环条件。找到后slow-next 是右半段第一个节点从 slow-next 开始反转。这时你可以顺手 slow-next nullptr 做断链。我个人的建议是刷题时用方式A就够了思路少容易手稳但如果你想追求代码的“可解释性”方式B更清晰。两种方式我都贴一遍这样大家在不同场景可以选自己习惯的。3.5 双指针同步遍历最后的临门一脚反转完成后我们有了两个链表的头指针first原链表的 head和 second反转后链表的头。现在相当于有两条独立的链表我们要做的就是把 first 和 second 同步往前走一节节地配对求和。循环条件很简单while(second) 或者 while(first)。因为两个链表的长度都是 n/2所以用哪个判断都可以。这里有个细节如果用 second 作为循环条件那么反转后第二段链表的尾节点的 next 恰好是 nullptr循环结束时 second 也是 nullptr完美退出。C完整实现看这里int pairSum(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } ListNode* prev nullptr; while (slow) { ListNode* next slow-next; slow-next prev; prev slow; slow next; } ListNode* first head; ListNode* second prev; int ans 0; while (second) { ans max(ans, first-val second-val); first first-next; second second-next; } return ans; }这段代码以方式A为基准简洁清楚时间复杂度O(n)空间复杂度O(1)已经是这道题的最优解。4. 实操记录完整题解路线图和易错点排查4.1 写代码前先画一遍链表状态图很多人在白板上写链表题容易翻车原因在于对指针的指向变化没有直观认识。我在动手敲代码之前一定会先在草稿纸上画一遍链表状态变化尤其是找中点。拿一个长度为6的链表举例1-2-3-4-5-6。两条直线分别代表 first 和 fast。fast 每次跳两个节点slow 每次走一个节点。跑完后 slow 在4fast 在空。这时右半段就是 4-5-6反转后变成 6-5-4。动手画一次你会发现first 从头出发时1和6对应2和5对应3和4对应。三组配对全部被我们覆盖了没有露网之鱼。这个认知感一旦建立代码只是背书而已。4.2 常见错误空指针、漏循环、断错链链表题的错误大多是空指针访问。这道题常见的翻车点有三个。第一个是快慢指针循环结束条件写错。比如 while(fast-next fast-next-next)如果链表只有两个节点fast 初始在 headfast-next 不为空fast-next-next 为空循环不进slow 保持在 head此时 slow 停在左半段最后一个节点。这个行为是符合预期的但如果你本意是想让 slow 停在右半段第一个节点那就错了。所以循环条件必须和你的定位意图匹配。第二个是反转后忘记第二段链表的头是 prev 还是 slow。很多人第一次写反转会被最后的指针状态搞晕。在反转模板中循环结束后 prev 指向原链表的最后一个节点也是反转后的新头。所以遍历时应该用 prev 而不是 slow因为 slow 在循环结束时已经是 nullptr 了这是低级错误里最高发的一个。第三个是同步遍历时用了错误的循环次数比如 while(first-next) 或者 while(first-next second-next)。这里的 n/2 次遍历用 while(second) 最稳因为 second 链表的尾部天然是 nullptr不需要额外计数。如果你用的是 while(first)也以 nullptr 为边界同样没问题。最忌讳的是用“n/2”这种需要额外计数的方式因为链表的长度需要先遍历一遍才知道凭空多了一次 O(n)没有意义。4.3 内存问题C 解法务必手动管理好节点C 刷题虽然力扣环境会统一回收内存但如果你把代码拿到本地或者面试环境去跑反转后的链表已经和原链表共享了一部分节点对象你要格外小心二次释放的问题。比如原链表的所有节点如果由一个容器统一管理反转只是改动了 next 指针并没有新增节点。所以程序最后只需要释放从头节点开始的那一条链即可。但断链操作会让这条链少了一部分剩下那部分如果没人管就会内存泄漏。这就引出我前面说的建议不追求极端的话用方式A不主动断链反而更省心因为原链表的所有节点仍然在一条链上回收也方便。但如果你用了方式B主动断链记得要分别释放两段链表的所有节点。很多题解不会谈这一点因为 LeetCode 环境不检查内存泄漏但实际工程里这就是隐患。我写嵌入式链表代码时被内存问题坑过不少次所以这个点我在刷题时就特别留意。4.4 边界条件测试清单每次写完链表题我都会拿几个特殊数组测一下长度为2的最小链表长度为4所有值相同的链表长度为6前半段全小值、后半段全大值的链表节点值为负数的情况为什么要测负数因为如果初始答案设为 0而所有值都是负数正确结果应该是负数你用 0 初始化就错了。最佳实践是用 INT_MIN 或者让答案等于第一组孪生和之后再逐步更新。这个细节在力扣这类题目里其实不太重要因为题目给的取值范围包含了正数但面试时能提一句“我用 INT_MIN 初始化避免全负数的情况”会显得你工程素养不错。长度为2的链表是个特别容易出问题的测试快慢指针在 while(fast fast-next) 条件下fast 第一步到了空slow 到了第二个节点。反转后second 指向第二个节点first 还是第一个节点循环走一次就结束答案就是两个节点之和。逻辑完全正确。4.5 复杂度分析为什么说这个解法是最优时间复杂度方面找中点跑了一遍链表O(n)反转后半段也跑了半条链O(n/2)同步遍历又跑了半条链O(n/2)。所以总时间复杂度是 O(n)。空间复杂度方面整个求解过程只用了常数个指针变量没有额外数组没有递归所以是 O(1)。你可能想既然转数组也是 O(n)为什么非要用 O(1) 空间这里有两个层面的回答。第一个层面是“面试表现”面试官看到你用 O(1) 空间解出来会认为你对链表的操作足够熟悉而不是只会依赖数组。第二个层面是“实际工程的价值”在内存受限的嵌入式环境或者处理超大链表时O(n) 的额外空间可能就是不可接受的。这道题能帮你把反转链表和快慢指针这两个高频技巧一次练到位性价比极高。5. 衍生思考这道题背后的链表基本功池5.1 从孪生和到回文链表的迁移做完这道题你会发现它的解题路径和“回文链表”惊人地相似。判断一个链表是不是回文经典做法也是找中点、反转后半段、然后两端同步比较。区别仅仅是回文链表比较的是值是否相等孪生和求的是相加的最大值。这个迁移很有价值。因为面试官在考链表的时候非常爱出回文链表如果你已经彻底掌握了2130题回文链表就是换个判断条件而已。我还建议你顺便想一想如果要求每对孪生节点求和之后再求这些和的中位数该怎么做这就变成“找中点反转收集到数组排序”的综合题了刷题广度就是这样一点点扩开的。5.2 如果链表不是单链表而是双向链表呢双向链表做这道题会简单很多因为 tail 能直接往前找前任节点本质上不用反转。你能从“从尾部往前指”这个思路反推为什么单链表需要反转——就是因为单链表只有 next 指针没有 prev没法从后往前走。理解了这一点你就理解了反转是“绕路模拟双链表”的本质。在面试现场说清楚这个逻辑比背模板更有说服力。5.3 从链表操作到工程项目嵌入式场景怎么用链表不只是刷题用的抽象结构实际工程中链表的操作模式在嵌入式内核、内存管理、缓存淘汰策略里都非常常见。比如 LRU 缓存的核心操作就是把节点从链表中间摘下来放到头部这需要“找前驱”和“重接指针”和反转链表时的指针重连是同一套功夫。我举一个具体场景嵌入式系统里常用空闲链表来管理内存块操作系统分配内存时就要遍历这个链表找到合适大小的块并摘下来归还内存时又要把块插回链表的对应位置。这些操作和力扣里的插入删除没有任何本质区别只是代码风格更工程化多了很多条件判断和错误处理。所以我刷链表题的时候从来不是刷完就扔而是每次都在想“这套指针操作放到我的嵌入式代码里怎么改”。6. 总结我的实操心得刷这道题的正确姿势如果你正在准备面试或者想在链表专题上打好底子我建议你用下面的顺序来完成这道题。第一遍先用数组法做一遍确保你理解了孪生配对到底怎么配对。第二遍尝试自己推导出快慢指针加反转的思路不要一开始就看题解。如果你能独立把这个思路想出来说明你对链表操作已经有感觉了。第三遍把代码写完分别测长度为2、4、6的链表以及全负数节点值。第四遍尝试把代码改写成方式B断链版本理解两种实现之间的差异。我只说一遍别走马观花这道题练熟之后我敢说链表中点、链表反转、双指针遍历这三个专题你都能过关。很多人在力扣刷题刷到后面发现自己一直在做会的题这是最无效的刷题方式。像这种一道题能顶上三道题的知识密度的题目才是真正值得反复琢磨的。根据我个人的经验链表反转这个操作看似简单但每次隔一段时间不写重新上手总会有一瞬间的卡壳。所以我的建议是不要只看题解一定要自己亲手画一遍链表状态变化图亲手写一遍每个指针的移动过程。这样才能把模板变成你肌肉记忆里的一部分面试手撕代码时才不会慌乱。