LeetCode29 - 删除链表的倒数第 N 个节点

📝 题目描述

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

示例：

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

💡 解题思路

方法一：计算长度

一种容易想到的方法是，我们首先从头节点开始对链表进行一次遍历，得到链表的长度 $L$ 。随后我们再从头节点开始对链表进行一次遍历，当遍历到第 $L−n$ 个节点时，它就是我们需要删除的节点。

为了方便实操，我们在头节点前再添加一个哨兵节点，这样得到 $L$ 后，我们从哨兵节点开始对链表进行一次遍历，当遍历到第 $L−n$ 个节点时，它就是我们需要删除的节点的前一个节点。

方法二：栈

我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则，我们弹出栈的第 n 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。这样一来，删除操作就变得十分方便了。

方法三：快慢指针

创建哨兵节点后，考虑创建一个 fast 和 slow 指针，分别都指向哨兵节点。

接下来，我们让 fast 先遍历 n 个节点，然后 slow 再开始遍历。

这样一来，当 fast 为 nullptr 时，slow 正好指向要删除的节点，如下图所示。

为了更方便实操，在实际代码中，设置当 fast -> next 为 nullptr 时，停止遍历，此时slow 正好指向要删除的节点的前一个节点。

🔧 代码实现

1、计算长度

/**
 * 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) {
        int L = 0;
        // 创建哨兵节点
        ListNode* headNode = new ListNode(-1, head);
        ListNode* ptr = head;
        // 计算链表长度
        while (ptr != nullptr) {
            L++;
            ptr = ptr -> next;
        }
        ptr = headNode;
        // 从哨兵节点开始走L - n步，到达要删除节点前的一个节点
        for (int i = 0; i < L - n; i++) {
            ptr = ptr -> next;
        }

        ptr -> next = ptr -> next -> next;
        ListNode* ans= headNode -> next;
        delete headNode;
        return ans;
    }
};

2、栈

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        stack<ListNode*> stk;
        ListNode* cur = dummy;
        while (cur) {
            stk.push(cur);
            cur = cur->next;
        }
        for (int i = 0; i < n; ++i) {
            stk.pop();
        }
        ListNode* prev = stk.top();
        prev->next = prev->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

3、快慢指针

/**
 * 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* headNode = new ListNode(-1, head);
        // 快慢指针都指向哨兵节点
        ListNode* fast = headNode, *slow = headNode;
        // fast提前遍历n个
        while (n > 0) {
            fast = fast -> next;
            n--;
        }
        // 当fast的下一个就是nullptr时，slow的下一个就是要删除的
        while (fast -> next != nullptr) {
            slow = slow -> next;
            fast = fast -> next;
        }

        slow -> next = slow -> next -> next;
        ListNode* ans = headNode -> next;
        delete headNode;
        return ans;
    }
};

📊 复杂度分析

1、计算长度

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

2、栈

时间复杂度： $O(L)$ ，其中 L 是链表的长度。
空间复杂度： $O(L)$ ，其中 L 是链表的长度，主要为栈的开销。

3、快慢指针

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

🎯 总结

核心思想：记住哨兵节点。