题目描述

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

样例

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

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

算法1

计算链表长度 $O(L)$

先循环⼀次拿到链表的总⻓度，
然后循环到要删除的结点的前⼀个节点 (前驱节点)，
跳过目标节点，
利用哑节点，避免头部情况
dummy 1 2 3 4 5 NULL

一次遍历链表，得到链表大小 size = 5，我们要删除第 size + 1 - n 个节点；

• 从 i=0, 跳1步可以跳到第2个点, 跳2步可以跳到第3个点

• 倒数第( n )个点是正数第(size-n+1)个点

• 倒数第(n+1)个点是正数第(size-n)个点

• 即跳(size-n-1)步可以跳到倒数第(n+1)个点

时间复杂度

• 时间复杂度：$O(L)$，其中 L 是链表的长度。

• 空间复杂度：$O(1)$。

C++ 代码

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        auto dummy = new ListNode(-1);
        dummy->next = head;

        int size = 0;
        for (auto p= head; p; p = p->next)  size++;

        auto p = head;
        // 找到倒数第(n+1)个点，是正数第(size-n)个点
        // 算个数时不包括虚拟头节点。
        for (int i = 0; i < size - n - 1; i++)  p = p->next;
        p->next = p->next->next;

        return dummy->next;
    }
};

算法2

(双指针 / 快慢指针) $O(L)$

• 关键字：倒数第 n 个
• 模式识别：
• 涉及链表的特殊位置，考虑快慢指针
• 要删除链表节点，找到它的前驱

这道题有⼀种特别简单的解法。设置 2 个指针，⼀个指针距离前⼀个指针 n 个距离。同时移动 2 个指
针， 2 个指针都移动相同的距离。当⼀个指针移动到了终点，那么前⼀个指针就是倒数第 n 个节点了。

比如，设置两个指针 p, q，让 q 先走 n 步，然后 p 和 q 一起走，直到 q 走到尾结点。

时间复杂度

• 时间复杂度：$O(L)$，其中 L 是链表的长度。

• 空间复杂度：$O(1)$。

参考文献

力扣视频题解

C++ 代码

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        // q 快指针， p 慢指针
        ListNode *p = dummy, *q = dummy;

        for (int i = 0; i < n + 1; i++) // q 先走 n+1 步
            q = q->next;

        while (q) { // 一起走
            p = p->next;
            q = q->next;
        }

        p->next = p->next->next;

        return dummy->next;
    }
};