题目描述

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

样例

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

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

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

限制

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

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

算法1

(两次遍历)

1. 第一次遍历求出链表长度。
2. 第二次遍历删掉指定结点。
3. 在 head 前新增 dummy 节点的方式避免删除首结点时出现问题。

时间复杂度

• 遍历两次链表，故时间复杂度为 $O(sz)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy = new ListNode(0, head);

        int sz = 0;
        for (ListNode *p = dummy; p; p = p->next)
            sz++;

        for (ListNode *p = dummy; p; p = p->next) {
            sz--;
            if (n == sz) {
                p->next = p->next->next;

                break;
            }
        }

        return dummy->next;
    }
};

算法2

(一次遍历)

1. 一次遍历的思路是设置两个指针，让其中一个指针先走 $n$ 步，然后两个指针再同时走。当第二个指针走到最后时，第一个指针的位置就是需要被删除的节点。
2. 在 head 前添加 dummy 节点，避免出现边界问题。
3. 设置两个指针 $p_1$ 和 $p_2$，均初始化为 dummy 节点。
4. $p_2$ 指针先移动 $n$ 次，然后 $p_1$ 和 $p_2$ 指针同时向后移动，直到 $p_2$ 指向最后一个节点。
5. 此时 $p_1$ 结点指向的下一个结点需要删除。

时间复杂度

• 两个指针同时遍历一次链表，故时间复杂度为 $O(sz)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy = new ListNode(0, head);

        ListNode *p1 = dummy, *p2 = dummy;
        while (n--)
            p2 = p2->next;

        while (p2->next) {
            p1 = p1->next;
            p2 = p2->next;
        }

        p1->next = p1->next->next;

        return dummy->next;
    }
};