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

快慢指针，https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

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

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

python

from typing import Optional
#Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # 创建哑结点（dummy）以处理头结点可能被删除的情况
        dummy = ListNode(0)
        dummy.next = head
        fast = slow = dummy

        # 快指针先前进 n+1 步
        for _ in range(n + 1):
            fast = fast.next

        # 快慢指针同时移动直到快指针到达链表末尾
        while fast:
            fast = fast.next
            slow = slow.next

        # 此时慢指针的下一个结点是要删除的结点
        slow.next = slow.next.next

        # 返回头结点
        return dummy.next

# 测试用例
def print_list(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

if __name__ == '__main__':
    head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    sol = Solution()
    print(print_list(sol.removeNthFromEnd(head, 2)))  # 输出：[1, 2, 3, 5]

    head = ListNode(1)
    print(print_list(sol.removeNthFromEnd(head, 1)))  # 输出：[]

    head = ListNode(1, ListNode(2))
    print(print_list(sol.removeNthFromEnd(head, 1)))  # 输出：[1]

这段代码实现了一个经典的链表算法题：删除链表的倒数第 N 个结点。

“快慢指针”配合“虚拟头结点（Dummy Node）”的解法。这种写法非常标准，能够优雅地处理删除头结点等边界情况。

下面我为你详细解读这段代码的核心逻辑和执行过程。

核心思路：快慢指针与虚拟头结点

这段代码主要利用了三个关键技巧：

虚拟头结点 (Dummy Node)：创建一个假的头结点指向真实的 head。这样做的好处是，无论我们要删除的是中间的节点还是第一个节点，操作逻辑都是统一的（都是修改前一个节点的 next 指针），避免了单独处理头结点的麻烦。
双指针 (Two Pointers)：定义 fast 和 slow 两个指针。
间距控制：通过让 fast 指针先走 n+1 步，使得 fast 和 slow 之间保持固定的距离。当 fast 到达链表末尾（None）时，slow 刚好停在待删除节点的前一个位置。

建立间距

python

for _ in range(n + 1):
    fast = fast.next

关键点：这里循环了 n + 1 次。
为什么要 n+1？ 我们的目标是让 slow 停在待删除节点的前驱节点上。
假设链表长度为 $L$ ，我们要删除倒数第 $n$ 个。那么待删除节点的前驱节点距离头部的步数是 $L - n$ 。
为了让 slow 走到 $L - n$ 的位置，我们需要让 fast 比 slow 多走 $n + 1$ 步。这样当 fast 走到链表尽头（即走了 $L + 1$ 步到达 None）时，slow 刚好走了 $(L + 1) - (n + 1) = L - n$ 步，正好位于目标位置。

复杂度分析

时间复杂度: $O (L)$ ，其中 $L$ 是链表的长度。虽然代码看起来有两段循环，但 fast 指针总共只遍历了一次链表（先走了 n+1 步，又走了剩余步数），所以是单次遍历。
空间复杂度: $O (1)$ 。只使用了 dummy, fast, slow 几个指针变量，没有使用额外的存储空间。

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

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