删除链表的中间节点 图解题解
这道题到底在问什么
- 输入
- head=[1,3,4,7,1,2,6]
- 输出
- [1,3,4,1,2,6]
- 输入
- head=[5]
- 输出
- [](删完为空)
- 输入
- head=[]
- 输出
- []
最优解：一步一步想明白
- 3记住「fast 两步、slow 一步,fast 到尾时 slow 在中点;prev 记着它前一个,改一根指针就删掉」,下面逐帧套它。
- 4先看整条链表 1→3→4→7→1→2→6,一共 7 个节点。中间下标是 ⌊7/2⌋=3,正是值 7 这个节点(蓝色),它就是我们要删掉的目标。下面用快慢指针把它一趟找出来。
- 5slow 和 fast 都站在头节点 1(下标 0),prev 还是空的。约定:每轮先把 prev 更新成当前 slow,再让 slow 走一步、fast 走两步。
- 6第 1 轮检查:fast 在节点 1,它的下一个 3 还在,说明没到尾。这一轮:先把 prev 记成当前 slow(节点 1),再让 slow 走一步、fast 走两步。
- 7走完:prev 落在节点 1、slow 到节点 3、fast 到节点 4。fast 还没到尾,继续下一轮。
- 8第 2 轮检查:fast 在节点 4,它的下一个 7 还在,说明没到尾。这一轮:先把 prev 记成当前 slow(节点 3),再让 slow 走一步、fast 走两步。
- 9走完:prev 落在节点 3、slow 到节点 4、fast 到节点 1。fast 还没到尾,继续下一轮。
- 10第 3 轮检查:fast 在节点 1,它的下一个 2 还在,说明没到尾。这一轮:先把 prev 记成当前 slow(节点 4),再让 slow 走一步、fast 走两步。
- 11走完:prev 落在节点 4、slow 到节点 7、fast 到节点 6。此刻 fast 已是链尾、它没有下一个了,循环到此结束。
- 12循环停下,slow 正好停在中间节点(值 7、下标 3=⌊7/2⌋,蓝色),prev 是它的前一个(值 4)。两个关键端点都拿到了,接下来动手删。
- 13删除第一步:prev(节点 4)原来的 next 指向中间节点 7,先把这条箭头断开。中间节点 7(灰色)准备旁路掉。
- 14删除第二步:把 prev.next 改成中间节点的下一个(slow.next),也就是让节点 4 直接接到 1。中间节点 7 没有任何指针指向它,就被旁路删掉了,链表变成 1→3→4→1→2→6。
- 15删除完成:链表是 1→3→4→1→2→6,中间的值 7 已删。回头看,我们只用快慢指针走了一趟就定位了中间节点和它的前驱,再改一根指针收工,额外空间 O(1)。
⚠️ 容易写错的地方
✗ 错：只找中间节点、没记前驱
✓ 对：用 prev 记住 slow 的前一个
删除要改的是前驱的 next(prev.next=slow.next),没有 prev 就无法把中间节点旁路
✗ 错：循环条件写成 while fast
✓ 对：while fast 且 fast.next
只判 fast 会让 slow 多走一步、落到中点之后,删错节点
✗ 错：漏掉单节点 / 空链表
✓ 对：开头判 head 为空或 head.next 为空就返回空
单节点的中间就是它自己,删完应为空;不判会在 prev 为空时崩
完整代码（Python / C++ / Java）
Python
from typing import Optional, List
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class 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 headC++
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* deleteMiddle(ListNode* head) {
if (!head || !head->next) return nullptr;
ListNode *slow = head, *fast = head, *prev = nullptr;
while (fast && fast->next) {
prev = slow; slow = slow->next; fast = fast->next->next;
}
prev->next = slow->next;
return head;
}
};Java
import java.util.*;
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
public ListNode deleteMiddle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head, fast = head, prev = null;
while (fast != null && fast.next != null) {
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 三个指针,原地改链、不开额外结构
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 删除链表的中间节点 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能不用 prev,直接用 slow 删?+
可以换个写法:让 fast 起步时先走一步(或循环条件改成 fast.next 且 fast.next.next),使 slow 最终停在中间节点的前一个,这样直接 slow.next=slow.next.next 就删了。本质都是要拿到「中间节点的前驱」,要么显式记 prev,要么让 slow 停早一格。
为什么 fast 两步、slow 一步就能找到中点?+
fast 的速度是 slow 的两倍,fast 走到链尾(约 n 步)时,slow 走了约 n/2 步,正好在中间。下标具体落在 ⌊n/2⌋ 还是 ⌈n/2⌉,取决于初始位置和循环条件的细节,本题让它落在 ⌊n/2⌋。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 删除链表的中间节点 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。