【LeetCode19. 删除链表的倒数第 N 个结点】——链表，快慢双指针，虚拟头结点、利用栈

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

思路：

本题是对链表中倒数N个结点的删除，数组中结点的删除在之前我们就接触过，而此处，是按照结点的位置来删除节点。对于链表而言，做查找第n个结点的操作是比数组要繁琐的，为了降低时间复杂度，在一次遍历内就完成题目所需要求，我们可以用到快慢双指针。同样的，我们也可以使用栈来求解。

暴力求解（求出链表长度）：

其实最直接的方法就是，将链表的长度L求出来，这样就直接移动L-n个结点，下一位就是要删除的结点。

class Solution {
public:
    int getLength(ListNode* head) {
        int length = 0;
        while (head) {
            ++length;
            head = head->next;
        }
        return length;
    }

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode* cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur->next;
        }
        cur->next = cur->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

快慢双指针：

在使用快慢双指针前，我们可以添加一个虚拟头结点，防止在删除头结点后出现的空指针情况。否则的话，我们需要讨论删除头结点以及删除非头结点这两种不同情况，比较繁琐。

我们可以让快指针先移动n个单位，接着让快慢指针同时移动，直至快指针到达尾部。此时，慢指针所移动的结点数就是链表长度-n，慢指针的下一位就是我们要删除的结点。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0); //设置虚拟头结点
        dummyHead->next = head;
        ListNode* slow = dummyHead; //定义快慢指针
        ListNode* fast = dummyHead;
        for (int i = 0; i < n; i++) //快指针先移动n个单位
        {
            fast = fast->next;
        }
        while (fast->next != NULL) //快慢指针同时移动，直至快指针到达尾部
        {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next; //删除节点
        return dummyHead->next;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

利用栈：

先将所有结点存入栈中，再巧妙利用栈先进后出的特性，找到要删除的结点。

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(); //出栈倒数n个结点
        }
        ListNode* prev = stk.top(); //指向倒数n个结点的前一个结点
        prev->next = prev->next->next; //删除节点操作
        ListNode* ans = dummy->next;
        delete dummy; //销毁虚拟头结点
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

往期回顾：
LeetCode24. 两两交换链表中的节点
LeetCode206. 反转链表
LeetCode707.设计链表
LeetCode203.移除链表元素
LeetCode54. 螺旋矩阵
LeetCode59.螺旋矩阵II
LeetCode977.有序数组的平方
LeetCode844.比较含退格的字符串
LeetCode283.移动零
LeetCode27.移除元素
LeetCode26.删除有序数组中的重复项
LeetCode209.长度最小的子数组
LeetCode904. 水果成篮
LeetCode242.有效的字母异位词
LeetCode76.最小覆盖子串