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

力扣题目链接 (opens new window)

题目描述

给你一个链表，删除链表的倒数第 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

进阶： 你能尝试使用一趟扫描实现吗？

思路

如果先遍历链表得到长度 len，倒数第 n 个结点就是正数第 len - n + 1 个结点，再遍历一次就能删除。这种方法没有问题，但需要扫描两趟链表。

怎样只扫描一趟呢？

本题要找的是“倒数第 n 个结点”。从链表末尾倒着数并不方便，但如果有两个指针始终保持固定间距，当快指针走到末尾时，慢指针的位置就可以由这个间距推出来。

那么快慢指针之间应该间隔多少？

我们真正需要找到的不是待删除结点，而是待删除结点的前一个结点。只有找到它，才能执行：

slow->next = slow->next->next;

具体做法如下：

1. 创建虚拟头结点 dummy，让 dummy->next = head
2. fast 和 slow 都从 dummy 出发
3. 先让 fast 向前移动 n 步
4. 当 fast->next != nullptr 时，fast 和 slow 同时向前移动
5. 循环结束时，fast 指向链表最后一个结点，slow->next 正好是倒数第 n 个结点

这里最容易写错的是循环条件。为什么是 fast->next != nullptr，而不是 fast != nullptr？

因为我们让 fast 最终停在尾结点，这样 slow 才会停在待删除结点的前一个结点。如果让 fast 走到空，slow 也会多走一步。

还有一个关键问题：为什么要使用虚拟头结点？

如果删除的正好是原链表的头结点，头结点之前没有结点可以操作。加上 dummy 后，删除头结点和删除其他结点就完全统一了，最后返回 dummy.next 即可。

快指针先走 n 步，快慢指针再同步移动，这个固定间距就是一趟扫描的核心。

模拟过程

以 head = [1,2,3,4,5]、n = 2 为例。

先创建虚拟头结点，fast 和 slow 都指向 dummy。让 fast 先走两步，此时 fast 指向结点 2，两个指针之间保持两步的距离。

接下来让 fast 和 slow 同时向后移动。相同规则连续执行三次后，fast 指向尾结点 5，slow 指向结点 3。

此时 slow->next 指向结点 4，它正是倒数第 2 个结点。让结点 3 直接指向结点 5，结点 4 就从链表中删除了，最终结果为 [1,2,3,5]。

很多录友会纠结到底让 fast 先走 n 步还是 n + 1 步。两种写法都可以，但循环条件必须配套：

• 先走 n 步，就在 fast->next != nullptr 时同步移动
• 先走 n + 1 步，就在 fast != nullptr 时同步移动

本篇采用第一种写法，fast 最后停在尾结点，更容易观察快慢指针的固定间距。

解题代码

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0, head); // 虚拟头结点，统一删除头结点的情况
        ListNode* fast = &dummy;
        ListNode* slow = &dummy;

        // fast 先走 n 步，与 slow 保持固定间距
        for (int i = 0; i < n; ++i) {
            fast = fast->next;
        }

        // fast 停在尾结点时，slow 恰好停在待删结点的前一个结点
        while (fast->next != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }

        ListNode* target = slow->next;
        slow->next = target->next;
        delete target;

        return dummy.next;
    }
};

复杂度分析

时间复杂度：O(L)，其中 L 是链表长度，每个指针最多遍历一次链表。

空间复杂度：O(1)，只使用了常数个指针。

其他语言

Python3

class Solution:
    def removeNthFromEnd(self, head, n):
        dummy = ListNode(0, head)
        fast = slow = dummy

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

        while fast.next:
            fast = fast.next
            slow = slow.next

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

Java

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy;
        ListNode slow = dummy;

        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;
        return dummy.next;
    }
}

Go

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Val: 0, Next: head}
    fast, slow := dummy, dummy

    for i := 0; i < n; i++ {
        fast = fast.Next
    }

    for fast.Next != nil {
        fast = fast.Next
        slow = slow.Next
    }

    slow.Next = slow.Next.Next
    return dummy.Next
}

JS

var removeNthFromEnd = function(head, n) {
    const dummy = new ListNode(0, head);
    let fast = dummy;
    let slow = dummy;

    for (let i = 0; i < n; i++) {
        fast = fast.next;
    }

    while (fast.next !== null) {
        fast = fast.next;
        slow = slow.next;
    }

    slow.next = slow.next.next;
    return dummy.next;
};

与代码随想录联系

这道题把代码随想录链表章节中的两个高频技巧放到了一起：虚拟头结点处理删除边界，快慢指针通过固定间距定位结点。

建议录友们先练习203. 移除链表元素，理解为什么虚拟头结点可以统一删除操作；再结合206. 反转链表，熟悉改变 next 指向时的指针操作。完整版本可以继续阅读代码随想录的19. 删除链表的倒数第 N 个结点。