删除链表倒数第 N 个节点并分析时间和空间复杂度。

核心回答

用虚拟头节点加快慢指针，可以在 O(L) 时间、O(1)额外空间内删除倒数第n个节点，L是链表长度。

让fast、slow都从虚拟头节点出发，fast先走n步；随后两者同步前进，直到fast停在最后一个节点。此时slow正好位于待删除节点的前面，执行 slow.next = slow.next.next，最后返回 dummy.next。虚拟头节点让删除原头节点也能复用同一套逻辑。

为什么slow停在正确位置

把dummy记为位置0，实际节点依次为1到L。倒数第n个节点的位置是 L-n+1，因此要找到的前驱位置是 L-n。

fast先走n步后，始终比slow领先n个位置。当fast到位置L时，slow就位于 L-n。所以应该停止在 fast.next 为空的时候，而不是让fast继续走到空；否则在这套起点与步数下，slow会多走一步。

例如链表 1 → 2 → 3 → 4 → 5，n=2：fast先停在2，slow在dummy；同步前进3次后，fast在5、slow在3，跳过slow后面的4，得到 1 → 2 → 3 → 5。

不同实现也可以让fast从head出发、先走n步并以fast为空为停止条件。关键是起点、间距、停止位置配套，不能把两套写法的某一步混用。

Python实现

下面假设输入是无环单链表，n为整数。除原题保证的合法输入外，这个版本还对n不为正或超过链表长度时抛出异常，并在修改链接前完成检查。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def remove_nth_from_end(head, n):
    if n <= 0:
        raise ValueError("n must be positive")

    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n):
        if fast.next is None:
            raise ValueError("n exceeds list length")
        fast = fast.next

    while fast.next is not None:
        fast = fast.next
        slow = slow.next

    slow.next = slow.next.next
    return dummy.next

函数复用原节点，只改动目标前驱的一条next引用。返回值可能是新头，因此调用方应保存返回值；仅忽略返回值，会在删除原头时继续拿着旧的head。

复杂度与边界

fast沿链表向前，slow同步走剩余部分，总操作数与L成正比；只用固定数量引用和一个dummy，额外空间为常数。这里的“一趟”是没有先单独遍历计算长度，不是每个节点只允许被任何指针接触一次。

• n=1：slow最终停在尾节点前，删除尾节点。
• n=L：fast先到尾，slow仍在dummy，删除原头节点。
• 只有一个节点且n=1：返回None。
• 空链表或n超过长度：这个实现抛出ValueError，原链表不修改；在线判题若已保证合法，可按约定简化检查。

节点值重复不影响算法，因为它按位置改引用，不通过数值猜测待删除节点。Python中的对象是否回收还取决于其他引用；C++手动管理内存时，则需另行处理被移除节点与dummy的释放。

常见追问

先求长度再删除可以吗？

可以。先得到L，再走到 L-n 的前驱位置，仍是 O(L)时间、O(1)空间；快慢指针满足不预先计算长度的一趟扫描要求。

为什么不把后一个节点的值复制过来？

复制后继值再跳过后继，会改变节点与内容的对应关系，而且删除尾节点时没有后继可复制。本题已经能够找到前驱，直接改链接更准确。

参考资料