🎮 快慢指针找前驱，虚拟节点消特判

昨天村长把“对称之盾”爆出来后，乐得像个两百斤的傻子。听说他那 Steam Deck 的风扇嗡嗡转了一宿，隔着半堵墙都能听见装备界面循环播放的BGM。今天一大早，我正蹲在锅炉边添柴，寻思着要不要摸个鱼，院门“砰”地一声又被一脚踹开。

“小白！出Bug了！”村长冲进来，屏幕上还是昨天那条魔法项链，但这次画风突变——项链正中间的环正在疯狂闪烁刺眼的红光，还伴随着刺耳的警报声。

“你看！锻造台提示说，项链的能量回路必须重新平衡！”村长把屏幕怼到我脸上，唾沫星子差点喷我眼睛里，“要删掉正中间那个环！只有把它‘优化’掉，整条链子的对称性才能稳定，我的盾牌属性才能生效！”

我接过电脑，屏幕上那条项链依然排成一条直线，圆环之间用箭头连接。这次的任务不是求什么孪生和了，而是简单粗暴的物理超度——定位正中间的节点，把它从链上摘掉。如果节点数是奇数，中间只有一个；如果是偶数，中间有两个，取靠后的那个，也就是下标为 ⌊n/2⌋ 的那个。

“村长，这不就是经典的删除链表中间节点吗？快慢指针的老本行。”我撸起袖子，“只不过这次不是找中点本身，而是要找它的前驱节点——毕竟单向链表只认 next 不认 prev，要删掉中点，得让前一个节点直接跳过它，指向它的下一个节点，完成物理断联。”

快慢指针找前驱

我抄起键盘，开始盘逻辑。对付这种单链表找位置的活儿，还得是快慢指针这对老搭档—— fast 每次走两步，slow 每次走一步，等 fast 走到尽头，slow 刚好站在中间节点上。

不过这次有个小细节：我们要删的恰好就是中间节点本身。单向链表是个无情的数据结构——每个节点只认 next，不认 prev，想删谁，得先找到它的前任。为了让 slow 最终稳稳停在中间节点的前一个位置，我决定让 fast 抢跑两步——等 fast 跑到终点时，slow 自然就卡在前驱的位置上了。

def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # 边界情况：只有一个节点，删掉后链表为空
    if not head.next:
        return None
    
    slow, fast = head, head
    # fast 先走两步，让 slow 慢一拍，最终 slow 停在中间节点的前驱
    fast = fast.next.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # 物理断联：让前驱直接指向中间节点的下一个节点
    slow.next = slow.next.next
    return head

提交，AC。我把屏幕转过去，正准备向村长邀功：“搞定！中间的红环已经被抠掉了！”

“啪。” 后脑勺突然挨了轻轻一下。老勇者不知何时又出现在我身后，盯着我的代码。

“快慢指针找前驱，O(N) 时间，O(1) 空间，逻辑没毛病。” 他抿了一口茶，慢条斯理地说道，“但是小白啊，你的边界条件处理得不够优雅。你看，为了处理只有一个节点的情况，你硬生生在函数开头打了一个if补丁！这在架构设计里叫什么？这叫‘补丁式编程’！万一哪天需求变了，变成删倒数第二个节点，你是不是还得再打一排补丁？”

我愣在原地：“那……怎么改进？”

“虚拟头节点（Dummy Node）。” 老勇者微微一笑，“Dummy Node，链表题里的万能站位符。”

虚拟节点消特判

“在链表最前面加一个哑节点 dummy，不参与战斗，只负责站位。让 slow 从 dummy 出发，fast 从真正的 head 出发，同时走。这样一来，slow 天然比 fast 慢了一拍——不需要手动抢跑。而且不管要删的是不是真正的头节点，slow 永远指着被删节点的前驱，连 if not head.next 的特判都省了。最后返回 dummy.next，完美。”

def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # 引入虚拟头节点，消灭边界特判
    dummy = ListNode(0, head)
    
    # slow从dummy出发，fast从head出发
    slow, fast = dummy, head    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
    slow.next = slow.next.next
    return dummy.next

我思路瞬间清爽了，虚拟头结点就像一个站在队伍最前面的替补队员，不参与比赛，但保证排头有人。slow 和 fast 从不同起点同时出发，天然拉开了一拍的差距。原本那个让人头疼的‘头节点可能被删’或者‘单节点越界’的边界问题，全部被 dummy 给消化掉——代码从八行缩到六行，特判抹除，逻辑一马平川。

“虚拟头结点是链表题的万能润滑剂，” 老勇者拍了拍我的肩膀，“遇到删除操作，先想想能不能用 dummy 把边界条件统一掉。记住一句话：能少写一行特判，就少埋一个 Bug。”

两套解法记心间，村长大坑无尽头

村长那边，项链中间那个闪烁红光的环“咔嚓”一声碎裂消失，剩下两半自动接合，整条链子散发出稳定的蓝色光芒。对称之盾的属性面板刷新了——防御力后面多了一行金色小字：“已激活：链路平衡加成”。

老头激动得抱着机器原地蹦跶，“拿到了！平衡加成！我就知道删掉中间那个环管用！”

我靠在椅背上，端起茶杯。平心而论，“快指针抢跑 + 前驱定位” 的解法虽然多打了一个 if 补丁，但逻辑清晰、稳如老狗，每一步都清清楚楚；而老勇者的 Dummy Node 技巧也确实把原本需要特殊处理的边界条件化于无形，代码更短，逻辑更纯粹。我把两种写法并排收进魔法书，记了一笔：快慢指针找前驱，虚拟节点消特判。

看着村长心满意足地溜达出门的背影，我忍不住在心里嘀咕：村长这条魔法项链的副本连打了两天，每天解锁一个新花样。不知道明天锻造台会不会又整出什么链表操作的新皮肤——也许是指定位置插入？也许是每隔 k 个删一个？照这个趋势下去，迟早有一天他会拿着一条带环的链表跑来问我：“小白啊，你看这链子它怎么自己咬住尾巴了？”

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。