删除链表的倒数第 N 个结点

怎样从“链表 1→2→3→4→5,删除倒数第 2 个结点(值为 4)。”推导出 链表 · 快慢指针，并证明每次状态变化都不会漏掉答案？

中心结论：快指针先走 n+1 步,再与慢同步;快到头时 slow 恰在待删结点前一格。

删除链表中倒数第 n 个结点。

在本站主例中，链表 1→2→3→4→5,删除倒数第 2 个结点(值为 4)。

算法最终需要得到或观察：删除 4 后链表为 1→2→3→5。

复制整条链表或反复寻找前驱会重复走节点；哨兵和指针重连直接维护局部关系。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“链表指针接力”，明确答案需要观察什么。
2. 2状态只维护 dummy 头、slow/fast、剩余步数 n+1。
3. 3转移每一步按照 快指针先走 n+1 步,再与慢同步;快到头时 slow 恰在待删结点前一格。
4. 4收尾读取 删除 4 后链表为 1→2→3→5。，并复核边界与复杂度。

画清每根 next 指针改变前后的归属，再写代码。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：dummy 头、slow/fast、剩余步数 n+1。

这道题比较简单，先循环一次拿到链表的总长度，然后循环到要删除的结点的前一个结点开始删除操作。需要注意的一个特例是，有可能要删除头结点，要单独处理。

这道题有一种特别简单的解法。设置 2 个指针，一个指针距离前一个指针 n 个距离。同时移动 2 个指针，2 个指针都移动相同的距离。当一个指针移动到了终点，那么前一个指针就是倒数第 n 个节点了。

快指针先走 n+1 步,再与慢同步;快到头时 slow 恰在待删结点前一格。

执行过程中持续维护：dummy 头、slow/fast、剩余步数 n+1。

正确性依赖以下不变量：slow 与 fast 间距恒为 n+1,保证 slow 停在待删前驱。

面试时可以压缩为：dummy+快慢指针,fast 先走 n+1,slow/fast 同步,最后 slow.next=slow.next.next 一次删除。

落到当前题，执行机制可以压缩为：快指针先走 n+1 步,再与慢同步;快到头时 slow 恰在待删结点前一格。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入链表 1→2→3→4→5,删除倒数第 2 个结点(值为 4)。 因为：快指针先走 n+1 步,再与慢同步;快到头时 slow 恰在待删结点前一格。
2. 2dummy + 快慢指针dummy 方便删头结点。 因为：slow.next 就是要删的结点。
3. 3fast 前进到 2快指针先走。 因为：n+1 间距保证 slow 在待删结点前驱。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5快慢同步前进保持间距不变地移动。 因为：fast 到 null 时 slow.next 即倒数第 n 个。
6. 6快慢同步前进保持间距不变地移动。 因为：fast 到 null 时 slow.next 即倒数第 n 个。
7. 7删除 slow.next (倒数第 2 个)断链并跳过目标结点。 因为：一次扫描 O(n)。
8. 8收尾与复杂度删除 4 后链表为 1→2→3→5。 因为：时间 O(n) · 空间 O(1)。快指针先走 n+1 步,再与慢同步;快到头时 slow 恰在待删结点前一格。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// ListNode define
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

// 解法一
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummyHead := &ListNode{Next: head}
	preSlow, slow, fast := dummyHead, head, head
	for fast != nil {
		if n <= 0 {
			preSlow = slow
			slow = slow.Next
		}
		n--
		fast = fast.Next
	}
	preSlow.Next = slow.Next
	return dummyHead.Next
}

// 解法二
func removeNthFromEnd1(head *ListNode, n int) *ListNode {
	if head == nil {
		return nil
	}
	if n <= 0 {
		return head
	}
	current := head
	len := 0
	for current != nil {
		len++
		current = current.Next
	}
	if n > len {
		return head
	}
	if n == len {
		current := head
		head = head.Next
		current.Next = nil
		return head
	}
	current = head
	i := 0
	for current != nil {
		if i == len-n-1 {
			deleteNode := current.Next
			current.Next = current.Next.Next
			deleteNode.Next = nil
			break
		}
		i++
		current = current.Next
	}
	return head
}

func main() {
    // 1. 主例
    //    输入：mode="remove-nth", values=[1,2,3,4,5], n=2
    //    期望：删除 4 后链表为 1→2→3→5。
    //
    // 2. 失败 / 未命中
    //    检查：不建 dummy 时删头结点会特判失败。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC141 环形链表；LC876 链表的中间结点
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意链表 1→2→3→4→5,删除倒数第 2 个结点(值为 4)。
2. 2重复复制整条链表或反复寻找前驱会重复走节点；哨兵和指针重连直接维护局部关系。
3. 3优化快指针先走 n+1 步,再与慢同步;快到头时 slow 恰在待删结点前一格。
4. 4证明slow 与 fast 间距恒为 n+1,保证 slow 停在待删前驱。
5. 5复杂度时间 O(n)，空间 O(1)