题目描述
思路解析动画文字版
记住「fast 两步、slow 一步,fast 到尾时 slow 在中点;prev 记着它前一个,改一根指针就删掉」,下面逐帧套它。
先看整条链表 1→3→4→7→1→2→6,一共 7 个节点。中间下标是 ⌊7/2⌋=3,正是值 7 这个节点(蓝色),它就是我们要删掉的目标。下面用快慢指针把它一趟找出来。
slow 和 fast 都站在头节点 1(下标 0),prev 还是空的。约定:每轮先把 prev 更新成当前 slow,再让 slow 走一步、fast 走两步。
第 1 轮检查:fast 在节点 1,它的下一个 3 还在,说明没到尾。这一轮:先把 prev 记成当前 slow(节点 1),再让 slow 走一步、fast 走两步。
走完:prev 落在节点 1、slow 到节点 3、fast 到节点 4。fast 还没到尾,继续下一轮。
第 2 轮检查:fast 在节点 4,它的下一个 7 还在,说明没到尾。这一轮:先把 prev 记成当前 slow(节点 3),再让 slow 走一步、fast 走两步。
走完:prev 落在节点 3、slow 到节点 4、fast 到节点 1。fast 还没到尾,继续下一轮。
第 3 轮检查:fast 在节点 1,它的下一个 2 还在,说明没到尾。这一轮:先把 prev 记成当前 slow(节点 4),再让 slow 走一步、fast 走两步。
走完:prev 落在节点 4、slow 到节点 7、fast 到节点 6。此刻 fast 已是链尾、它没有下一个了,循环到此结束。
循环停下,slow 正好停在中间节点(值 7、下标 3=⌊7/2⌋,蓝色),prev 是它的前一个(值 4)。两个关键端点都拿到了,接下来动手删。
删除第一步:prev(节点 4)原来的 next 指向中间节点 7,先把这条箭头断开。中间节点 7(灰色)准备旁路掉。
删除第二步:把 prev.next 改成中间节点的下一个(slow.next),也就是让节点 4 直接接到 1。中间节点 7 没有任何指针指向它,就被旁路删掉了,链表变成 1→3→4→1→2→6。
删除完成:链表是 1→3→4→1→2→6,中间的值 7 已删。回头看,我们只用快慢指针走了一趟就定位了中间节点和它的前驱,再改一根指针收工,额外空间 O(1)。
边界:空链表原样返回;单节点删完为空;两节点删后一个。
两个追问:也可让 slow 停在中点前一个免去 prev;两倍速天然取中点。
参考代码
from typing import Optional, Listclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head or not head.next: return None slow = fast = head prev = None while fast and fast.next: prev = slow slow = slow.next fast = fast.next.next prev.next = slow.next return head复杂度
- 时间：O(n)，fast 每轮走两步,约 n/2 轮就到链尾,整体只遍历一趟,n 是链表长度
- 空间：O(1)，只用 slow、fast、prev 三个指针,原地改链、不开额外结构
易错点
面试追问把动画讲成自己的话
追问能不能不用 prev,直接用 slow 删?
追问为什么 fast 两步、slow 一步就能找到中点?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
链表最大孪生和
LeetCode 2130 · 中等 · 沿着 链表套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题