题目描述
思路解析动画文字版
记住「找中点 → 反转后半 → 左右对着加」,下面逐帧套它。关键在第二步:反转之后,原本的尾节点就跑到了后半段的最前面,正好和头节点配成第一对孪生。
第一步找中点。slow 和 fast 都从头节点(下标 0,值 5)出发。接下来 fast 每轮走两步、slow 每轮走一步。
看 fast(下标 0,值 5):它和它的 next 都还在,说明还没到尾,可以再走一轮。
走一轮:slow 前进一步到下标 1(值 4);fast 前进两步到 下标 2(值 2)。
看 fast(下标 2,值 2):它和它的 next 都还在,说明还没到尾,可以再走一轮。
走一轮:slow 前进一步到下标 2(值 2);fast 前进两步到 下标 4(值 6)。
看 fast(下标 4,值 6):它和它的 next 都还在,说明还没到尾,可以再走一轮。
走一轮:slow 前进一步到下标 3(值 3);fast 前进两步到 (已越过链尾)。
fast 已经越过链尾,循环停下。此刻 slow 停在下标 3(值 3),它正好是后半段的第一个节点。于是链一分为二:前半 [5, 4, 2]、后半 [3, 6, 1]。
第二步反转后半段。准备一个 prev,先置为空;cur 从后半段头(下标 3,值 3)开始。接下来一个个把箭头掉头。
第 1 步:先记住 cur(下标 3,值 3)的后继是 下标 4(值 6),再把 cur.next 掉头指向 prev(空)。它现在是反转后的尾。
第 2 步:先记住 cur(下标 4,值 6)的后继是 下标 5(值 1),再把 cur.next 掉头指向 prev(下标 3,值 3)。
第 3 步:先记住 cur(下标 5,值 1)的后继是 空(后半段到此为止),再把 cur.next 掉头指向 prev(下标 4,值 6)。
cur 变空,后半段反转完毕:现在它是 1→6→3。反转后的头 prev 落在下标 5(值 1),也就是原链表的尾节点。它马上要和原来的头节点配成第一对孪生。
第三步求孪生和。left 从原链表头(下标 0, 值 5)、right 从反转后的头(下标 5, 值 1)出发,同步往中间走。每一步 left.val + right.val 就是一对孪生和,用 ans 记最大值,ans 先置 0。
第 1 对孪生:left=5 配 right=1,孪生和 5 + 1 = 6。比当前 ans 大,ans 更新成 6。
这一对算好了,两个指针各往中间走一步:left 到下标 1(值 4)、right 到下标 4(值 6),准备下一对。
第 2 对孪生:left=4 配 right=6,孪生和 4 + 6 = 10。比当前 ans 大,ans 更新成 10。
这一对算好了,两个指针各往中间走一步:left 到下标 2(值 2)、right 到下标 3(值 3),准备下一对。
第 3 对孪生:left=2 配 right=3,孪生和 2 + 3 = 5。没超过当前 ans=10,ans 不变。
right 走到了空,说明所有孪生对都配完了,循环停下。每一对都比较过,ans 里就是最终答案。
三对孪生和分别是 6、10、5,最大的就是 10。回头看整趟:快慢指针一遍走到中点,后半段就地反转(没开新链),再左右对着相加一遍,全程只挪了几个指针,额外空间 O(1)。
边界:两节点即一对;全等则孪生和相等;题目保证偶数长。
两个追问:可用数组换 O(n) 空间;一般无需还原,要求还原就再反转回去。
参考代码
from typing import Optional, Listclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def pairSum(self, head: Optional[ListNode]) -> int: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next prev = None while slow: nxt = slow.next slow.next = prev prev = slow slow = nxt ans = 0 while prev: ans = max(ans, head.val + prev.val) head = head.next prev = prev.next return ans复杂度
- 时间：O(n)，找中点走半遍、反转后半段走半遍、左右双指针再走半遍,合计仍是线性 O(n)
- 空间：O(1)，只用 slow、fast、prev、cur 等几个指针,就地反转、不开新链或数组
易错点
面试追问把动画讲成自己的话
追问不反转链表,有别的解法吗?
追问做完题需要把链表恢复原样吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
合并零之间的节点
LeetCode 2181 · 中等 · 沿着 链表套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题