🎮快慢指针拆项链，递归回溯借东风
今天我正蹲在锅炉边享受难得的清静，熟悉的Steam Deck风扇声又由远及近地碾了过来。村长捧着电脑冲了进来，屏幕上闪烁着一条由圆环串联而成的项链，每个环上标着数字，还散发着淡蓝色的魔法光芒。
“小白！游戏里掉落了一条神秘的项链！“村长的眼睛比项链还亮，“你看，这链子一共 n 个环，n 还是偶数！游戏提示说蕴含什么对称的力量——从两头往中间数，第 i 个环和第 n-1-i 个环叫‘孪生环’！每对孪生环放在一起会产生能量共鸣，共鸣值就是两个环上的数字之和！需要找出最强共鸣值提交给锻造台，才能解锁传说中的对称之盾！”
我接过电脑，屏幕上那条项链排成一条直线，圆环之间用箭头连接——这不就是链表吗？偶数个节点，首尾对称配对，求最大孪生和。“村长，您直接把它塞进一个数组里，然后用个 for 循环，左边一个指针右边一个指针往中间夹击不就行了？”
村长一听，胡子都翘起来了：“糊涂！数组是什么？那是连续内存！这链子这么长，万一中间断了，你还得重新分配一大块连续的内存空间来存它！我们村的魔法锅炉用的就是碎片化内存管理，最忌讳动不动就开大数组！最好是 O(1) 空间复杂度，原地解决！”
我叹了口气，行吧，那只能对链表本身进行物理改造了。
斩链刀·反转术
梳理下思路：快慢指针找中点，反转后半段，然后前后同时遍历配对——正好是 O(n) 时间加 O(1) 空间。
我抄起键盘开干：快慢指针是老搭档了，fast 每次走两步，slow 每次走一步，当 fast 跑到终点时，slow 正好卡在中点。然后把后半段链表反转，让尾节点变成新头。最后前半段从原头出发，后半段从新头出发，一边走一边求和，max 一路追最大值。
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre, cur = None, head
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
def pairSum(self, head: Optional[ListNode]) -> int:
mid_node = self.middleNode(head)
second_head = self.reverseList(mid_node)
ans = 0
while second_head:
ans = max(ans, head.val + second_head.val)
head = head.next
second_head = second_head.next
return ans
提交，AC。“村长，这什么孪生环啊，分明是把链表反转加双指针的经典面试题穿上了魔法项链的皮肤！连‘对称之盾’这种道具名都起得跟算法术语似的。”我一边吐槽，一边我把计算出的最大孪生和报给村长：“是 10086！”
村长激动地一拍大腿：“好！我就知道这条项链大有玄机！你听听，10086——这数字多耳熟，我上个月充话费打的就是这个号！我得赶紧提交共鸣值，对称之盾在锻造台上已经冒金光了！”说罢，他便捧着电脑倒腾了起来。
回溯剑·递归道
“快慢指针加反转链表，O(n)时间，O(1)空间，写得不错。” 熟悉的声音从身后传来。
老勇者不知何时倚在了门框上，手里端着一杯枸杞茶，瞅着屏幕。他接着抿了一口茶，“但你有没有想过，你为了算个最大值，把人家好好的链表给拆了？这叫破坏性读取，懂不懂？”
我愣在原地：“可是村长说要 O(1) 空间……”
“O(1) 空间只是手段，不是目的。”老勇者放下茶杯，指尖在键盘上飞舞：
class Solution:
def pairSum(self, head: Optional[ListNode]) -> int:
left = head
ans = 0
def dfs(node):
if node:
# 先递归到底，node走到链表尾部
dfs(node.next)
# 回溯时，node 从尾向头走，left 从头向尾走，两者天然形成孪生配对
nonlocal left, ans
ans = max(ans, left.val + node.val)
left = left.next
dfs(head)
return ans
我盯着那段代码，瞳孔地震：“等等……这是……”
“没错。”老勇者微微一笑，“递归回溯。函数调用栈本身就是一条隐形的链表。利用调用栈天然的 LIFO 特性，当你一路递归到底再回溯上来时，node 是从尾部往头部走的，而我的 left 是从头部往尾部走的。两者在回溯过程中自然相遇——这不就是最完美的孪生配对吗？”
他顿了顿，悠悠地吐出一句：“不需要找中点，不需要反转链表，不需要手动维护三个指针。代码只有十几行，逻辑优雅得像首诗。”
确定vs优雅之辩
村长凑过来，盯着老勇者的那段代码，眉头拧成了麻花：“递归？链表用递归？不怕爆栈？你这 dfs(node.next) 一层套一层，万一这链子有十万个节点，一半也有五万层，到时候一个 StackOverflowError，连个报错信息都来不及打就炸了！这叫优雅？这这叫给评测机递刀子，给生产环境埋炸弹！“
他气的胡子一翘一翘的：“我告诉你，真正的工程化思维是什么？是确定性！是能跑在生产环境里不炸的稳定性！不是让你在这儿写什么‘回溯的诗’！诗能当饭吃吗？诗能让服务器不宕机吗？不能！”
面对村长唾沫横飞的“工程化”说教，老勇者连眼皮都没抬一下。他轻轻抿了口茶：“老村长啊，你只盯着爆栈的定时炸弹，却没看见迭代反转的副作用。小白那套快慢指针加反转链表的做法，原地把人家后半段链表的 next 全拧反了。这在算法设计里叫什么？这叫‘破坏性副作用’！“
老勇者的声音不大，却字字诛心：”如果在生产环境里，另一个线程正在遍历这条链表——比如统计它的长度——小白这一刀切下去，那个线程当场就得给你抛出一个 NullPointerException。递归虽然费栈，但它不修改原数据，是纯函数式的读操作，没有破坏性副作用。你管这叫定时炸弹，我倒觉得这是读写分离的架构美学。”
村长一听，胡子又翘了起来：“你跟我谈架构美学？我告诉你，在服务器机房里，内存就是命！你那一层层递归调用栈——五万层栈帧，每帧存局部变量和返回地址，空间开销是O(n)，比小白那O(1)的迭代反转多了一整个数量级！题目数据量小的时候你还能装优雅，数据量一上来，操作系统直接甩个 SIGSEGV 送你回老家！”
老勇者也不恼，只是慢条斯理地吹了吹茶杯里的热气：“迭代反转O(1)额外空间不假，但那是在原地修改的前提下——它把原链表拆了重装。如果这道题要求保留原链表不变，你那一套就得先拷贝再反转，空间一样O(n)。递归的回溯本质上是在调用栈上隐式地维护了一个‘从尾到头’的遍历顺序，不需要显式修改任何指针。你说它费栈，我说它省心。哪套方案更优，取决于约束条件，不是一棍子打死的事。”
两人你一言我一语，一个坚持“爆栈风险不可控”，一个反驳“并发环境下数据完整性更重要”，唾沫星子横飞，简直比代码评审会上架构师和SRE吵架还激烈。
我呆呆地坐在角落里，看着这两位大佬争得面红耳赤。半晌，我弱弱地举起手，试图打破这剑拔弩张的气氛：“那个……两位前辈……”
两人同时转过头：“说！！”
我咽了口唾沫，小声说道：“其实……这题如果用 Python 写的话，直接把链表转成列表，然后双指针从两头往中间夹击求最大值……不仅不用反转链表，也不用递归爆栈，而且运行速度比你们俩都快……”
空气突然安静了。
村长和老勇者对视了一眼，同时冷哼一声，异口同声地骂道：“闭嘴！！”
说完，两人一甩袖子，各自背着手气呼呼地走了出去，只留我一个人在风中凌乱。
所以……我这算不算是凭一己之力，终结了一场史诗级的技术辩论？
本作品采用
知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议
进行许可。