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

问题拆解

删除单链表的倒数第 n 个节点。链表没有下标，“倒数第 n”天然是个尴尬的问法：不走到尾部就不知道总长，最直接的做法是先遍历一遍数出长度 L，再从头走 L - n 步找到待删节点的前驱，两遍搞定。

题目进阶要求一遍扫描。既然拿不到总长，就换个思路制造“相对位置”：让两个指针保持 n 的固定间距同步前进，当前面那个走到链表末尾时，后面那个自然停在倒数第 n 个的附近。

删除节点需要的是它的前驱。让快指针从 dummy 先走 n + 1 步的等价形式是：快慢都从 dummy 出发，快先走 n 步，之后同走到快指针指向末尾 null 的前一格——此时慢指针正是待删节点的前驱。

dummy + 间隔 n 的快慢指针

待删的可能是头节点（比如链表长度恰好等于 n），它没有前驱，所以先挂一个 dummy 假头，让“删头”和“删中间”共用一套逻辑。

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode fast = dummy, slow = dummy;
    for (int i = 0; i < n; i++) { // 快指针先走 n 步，拉开间距
        fast = fast.next;
    }
    while (fast.next != null) { // 快指针到最后一个节点时停下
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next; // slow 是待删节点的前驱
    return dummy.next;
}

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n):  # 快指针先走 n 步，拉开间距
        fast = fast.next
    while fast.next:  # 快指针到最后一个节点时停下
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next  # slow 是待删节点的前驱
    return dummy.next

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    fast, slow := dummy, dummy
    for i := 0; i < n; i++ { // 快指针先走 n 步，拉开间距
        fast = fast.Next
    }
    for fast.Next != nil { // 快指针到最后一个节点时停下
        fast = fast.Next
        slow = slow.Next
    }
    slow.Next = slow.Next.Next // slow 是待删节点的前驱
    return dummy.Next
}

// Rust 的借用规则不允许快慢两个可变引用同时指向一条链，
// 这里改用等价的两遍法：先数长度，再走 len - n 步找到前驱。
pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
    let mut len = 0;
    let mut p = head.as_ref();
    while let Some(node) = p {
        len += 1;
        p = node.next.as_ref();
    }
    let mut dummy = Box::new(ListNode { val: 0, next: head });
    let mut cur = &mut dummy;
    for _ in 0..len - n {
        cur = cur.next.as_mut().unwrap();
    }
    // cur 是待删节点的前驱，摘下它并接上后继
    let removed = cur.next.take();
    cur.next = removed.and_then(|node| node.next);
    dummy.next
}

两个指针都从 dummy 出发是这套写法的关键。若从 head 出发，快指针先走 n 步后可能直接越过末尾（n 等于链表长度时），循环条件就要额外判空。而从 dummy 出发多垫了一格，快指针走完 n 步后至少还停在合法节点上，while fast.next 的条件恰好让慢指针停在前驱位置——差一步就会删错节点，这是本题最常见的 off-by-one。

Rust 版没有用快慢指针，因为慢指针要拿可变借用改 next，而快指针还持有同一条链的引用，借用检查器不允许。两遍法虽然多扫一次，但每个节点仍只被访问常数次，复杂度不变，换来的是纯安全代码。

复杂度

指标	复杂度	原因
时间	`O(L)`	快慢指针合计各走一遍；两遍法也是 2L 次访问
空间	`O(1)`	只用 dummy 和两个指针

可以迁移的模式

涉及“倒数第 k”的链表问题，用固定间距的双指针把它转成正向同步走；
可能删除头节点时，先挂 dummy，让所有节点都有前驱；
找“待删节点的前驱”而不是待删节点本身——单链表删除永远要站在前一格操作。

“先拉开间距再同步走”和 dummy 假头这两件套，是链表删除类题目的标准开局。