给定单链表头节点 head,删除链表的中间节点,并返回修改后的头节点。长度为 n 时,中间节点是 0-based 下标 ⌊n / 2⌋ 的节点。
class Solution:
def deleteMiddle(
self,
head: Optional[ListNode]
) -> Optional[ListNode]:
Unit 05 · 快慢指针:固定距离定位倒数节点
先让快指针从 dummy 出发领先 n+1 条边,再让快慢指针同步移动。当快指针到达 None 时,慢指针恰好停在待删除节点的前驱,只需改写一条 next 边。
给定一个链表,删除链表的倒数第 n 个结点,并返回链表头节点。
sz,满足 1 ≤ sz ≤ 30;1 ≤ n ≤ sz,节点值范围为 [0,100];O(sz),额外空间 O(1)。使用 dummy 统一删除头节点。快指针先领先 n+1 条边;同步移动结束后,slow.next 就是目标节点。
Unit 01:删除需要稳定前驱。
Unit 02:修改指针前保持后续可达。
Unit 04:通过前驱改写局部连接。
目标位置从末端定义,无法直接正向计数。用 fast 与 slow 的固定距离把“倒数位置”转成“前驱位置”。
稳定的虚拟头节点。即使删除原 head,slow 仍然可以停在目标节点的前驱。
先走 n+1 条边,再与 slow 同速移动。它负责感知链表末端。
同步阶段结束时停在待删除节点的前驱,而不是停在目标节点本身。
快慢指针之间保持 n+1 条边,使 fast 到达 None 时 slow.next 正好是倒数第 n 个节点。
从“固定距离定位倒数节点”迁移到“速度差定位中点”。删除动作不变,真正变化的是如何让 slow 停在目标节点前驱。
给定单链表头节点 head,删除链表的中间节点,并返回修改后的头节点。长度为 n 时,中间节点是 0-based 下标 ⌊n / 2⌋ 的节点。
class Solution:
def deleteMiddle(
self,
head: Optional[ListNode]
) -> Optional[ListNode]:
[1, 10⁵] 内;1 ≤ Node.val ≤ 10⁵;slow.next = slow.next.next完全相同slow = dummy、fast = head?目标是让 slow 始终保持“前驱”语义。
必须先确保第二步访问安全。
fast 速度是 slow 的两倍。
修改节点字段,而不是只移动局部变量。
中间下标为 3,目标值为 7。观察 slow 为什么停在值 4 的节点。
根据四个语义槽位完成函数。检查器关注结构语义,不要求变量命名与示例完全一致。
不会自动跳转。可继续复看官方样例或手动进入 Unit 06。