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

◎

本节目标

用固定间距的快慢指针一次扫描定位倒数第 N 个节点的前驱。

这道题是链表解题框架的第四道母题。题目从尾部给出位置，但链表只能向前走；关键是把尾部距离转换成两个指针之间固定的间距。

查看原题

题意与约束

给定链表头节点和合法的 n，删除倒数第 n 个节点并返回新头节点。若删除的是原头节点，返回值会改变；单节点链表且 n = 1 时结果为空。

第一反应

先建立 dummy -> head，让 slow、fast 都从虚拟头节点出发。让 fast 先走 n 步后，两指针保持这个间距同步前进；当 fast.next 为 null 时，slow.next 恰好是待删除节点。

因为 slow 停在待删除节点的前驱，执行 slow.next = slow.next.next 即可统一处理删除头节点和删除中间节点，无须额外分支。

间距推导

fast 比 slow 领先 n 个节点。同步移动直到 fast 到达最后一个节点时，slow 距最后一个节点仍有 n 步，因此它的后继正是倒数第 n 个节点。虚拟头节点保证当目标为原头节点时，仍然存在可修改的前驱。

代码实现

C++

C++17

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

        for (int step = 0; step < n; step++) {
            fast = fast->next;
        }
        while (fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return dummy.next;
    }
};

Python

Python 3

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

        for _ in range(n):
            fast = fast.next
        while fast.next is not None:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dummy.next

复杂度分析

• 时间复杂度：O(L)，快指针的预走和同步移动合计只扫描链表一次。
• 空间复杂度：O(1)，只使用虚拟头节点和两个指针。

常见误区

• 让快指针先走 n + 1 步，却仍使用同一停止条件，造成定位偏一位。
• 没有虚拟头节点，删除原头时遗漏返回新头的分支。
• 把 slow 停在目标节点本身，随后无法只通过一次改写跳过它。

模式迁移

固定间距可迁移到寻找倒数第 k 个节点及其他固定距离关系；当删除或区间改写的目标可能包含原头时，虚拟头节点都能提供统一的前驱。