第4章|链表

Unit 05 · 快慢指针:固定距离定位倒数节点

← Unit 04
仅本次页面有效
U05
Remove Nth From Enddummy · fast · slow · fixed gap

不知道链表有多长,
也能一次扫描找到倒数位置。

先让快指针从 dummy 出发领先 n+1 条边,再让快慢指针同步移动。当快指针到达 None 时,慢指针恰好停在待删除节点的前驱,只需改写一条 next 边。

已恢复本浏览器中的学习进度阶段、动画、代码、脚手架和滚动位置均已恢复。
LeetCode #19 题目模型删除位置由链表末端定义

题目要求

给定一个链表,删除链表的倒数第 n 个结点,并返回链表头节点。

class Solution: def removeNthFromEnd( self, head: Optional[ListNode], n: int ) -> Optional[ListNode]: pass

约束与复杂度目标

  • 链表节点数为 sz,满足 1 ≤ sz ≤ 30;
  • 1 ≤ n ≤ sz,节点值范围为 [0,100];
  • 进阶目标:只扫描链表一次,时间 O(sz),额外空间 O(1)。

示例

输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
输入:head = [1], n = 1
输出:[]
输入:head = [1,2], n = 1
输出:[1]

本页主模型

使用 dummy 统一删除头节点。快指针先领先 n+1 条边;同步移动结束后,slow.next 就是目标节点。

连接前四个 Unit:本题只新增“如何找到前驱”,删除动作仍然相同

已经掌握

Unit 01:删除需要稳定前驱。
Unit 02:修改指针前保持后续可达。
Unit 04:通过前驱改写局部连接。

→
本题新增

目标位置从末端定义,无法直接正向计数。用 fast 与 slow 的固定距离把“倒数位置”转成“前驱位置”。

dummy

稳定的虚拟头节点。即使删除原 head,slow 仍然可以停在目标节点的前驱。

fast

先走 n+1 条边,再与 slow 同速移动。它负责感知链表末端。

slow

同步阶段结束时停在待删除节点的前驱,而不是停在目标节点本身。

Fixed Gap

快慢指针之间保持 n+1 条边,使 fast 到达 None 时 slow.next 正好是倒数第 n 个节点。

认知任务 1
先确认:删除动作没有变,难点只是找到目标节点的前驱
无论目标位置从头部还是尾部定义,真正改变链表结构的仍是 predecessor.next = predecessor.next.next。
链表定位与删除动画状态 1 / 10

快慢指针间隔

fast 位置dummy
slow 位置dummy
节点访问次数0
本步覆盖 / 删除—
本步保持 / 建立—
创建 dummy
fast 领先 n+1
保持固定距离
fast 到 None
slow 定位前驱
绕过目标节点
点击“下一步”,观察 fast 如何把链表末端的信息传递给 slow。
阶段 1 / 6可随时返回,所有状态自动保存
关键表达式补全只填写 9 个关键位置
from typing import Optional class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def removeNthFromEnd(self, head, n): dummy = ListNode(0, ) fast = slow = for _ in range(): fast = while : fast = slow = slow.next = slow.next.next return
分层提示:先守住不变量,再写表达式
进入函数。
fast—
slow—
slow.next—
当前间隔0
返回入口n1
返回状态未返回
完成代码联动后进入脚手架迁移:LeetCode #2095 删除链表的中间节点代码正确或播放完整轨迹后解锁;查看提示与填入骨架不会解锁。
LeetCode 官方迁移题 · Medium

#2095 删除链表的中间节点

从“固定距离定位倒数节点”迁移到“速度差定位中点”。删除动作不变,真正变化的是如何让 slow 停在目标节点前驱。

打开官方原题 ↗
题目要求

给定单链表头节点 head,删除链表的中间节点,并返回修改后的头节点。长度为 n 时,中间节点是 0-based 下标 ⌊n / 2⌋ 的节点。

class Solution:
    def deleteMiddle(
        self,
        head: Optional[ListNode]
    ) -> Optional[ListNode]:
n = 1, 2, 3, 4, 5 时,中间下标依次为 0, 1, 1, 2, 2。
官方示例与约束
[1,3,4,7,1,2,6] → [1,3,4,1,2,6]
[1,2,3,4] → [1,2,4]
[2,1] → [2]
  • 节点数在 [1, 10⁵] 内;
  • 1 ≤ Node.val ≤ 10⁵;
  • 偶数长度删除第二个中间节点。

读题门槛:先确定题目的输出契约

链表 [1,2,3,4] 应删除哪个节点?
偶数长度使用下标 ⌊n/2⌋。
输入只有一个节点 [7] 时,返回什么?
唯一节点本身就是下标 0 的中间节点。

#19 → #2095:保留“定位前驱再绕过”,替换定位机制

维度#19 倒数第 N 个#2095 中间节点
目标定义由末端向前数 n由长度决定 ⌊n/2⌋
fast 的策略先领先 n+1,再同速从 head 出发,每轮走 2
slow 的职责停在倒数目标的前驱停在中间节点的前驱
删除动作slow.next = slow.next.next完全相同
边界结果n=长度时删除原 head长度 1 时删除唯一节点

为什么令 slow = dummy、fast = head?

观察长度为 1 时,中间节点前驱只能是 dummy。

不要背完整代码:先完成四个语义槽位

槽位 1 · 边界初始化怎样保证单节点也能删除?

目标是让 slow 始终保持“前驱”语义。

槽位 2 · 安全循环fast 每轮走两步,循环条件是什么?

必须先确保第二步访问安全。

槽位 3 · 速度差每轮如何推进?

fast 速度是 slow 的两倍。

槽位 4 · 删除与返回定位完成后做什么?

修改节点字段,而不是只移动局部变量。

结构组装尚未解锁完成四个槽位后,页面只展示由你已经选择的语义拼成的代码骨架。

官方样例轨迹:[1,3,4,7,1,2,6]

中间下标为 3,目标值为 7。观察 slow 为什么停在值 4 的节点。

1 / 6
slowdummy
fast1
slow.next1
动作初始化
slow 从 dummy 出发,fast 从 head 出发,预留一个节点的前驱偏移。

独立重写:不提供一键答案

根据四个语义槽位完成函数。检查器关注结构语义,不要求变量命名与示例完全一致。

先完成官方样例轨迹,再提交独立重写。
迁移分层提示
完成后停留在本页

不会自动跳转。可继续复看官方样例或手动进入 Unit 06。

手动进入 Unit 06 →
Unit 05 已完成。页面不会自动跳转;刷新后仍会回到当前学习位置。
触发信号位置从链表末端定义,无法直接正向定位
核心表示dummy + fast + slow + n+1 条边间隔
循环不变量同步阶段 fast 与 slow 间隔保持不变
删除动作slow.next = slow.next.next
常见错误只领先 n;slow 停在目标而非前驱;移动变量代替改边
迁移方向中点、固定窗口、环与位置差