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

前言

题目： 19. 删除链表的倒数第N个结点
文档： 代码随想录——删除链表的倒数第N个结点
编程语言： 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* dummyHead = new ListNode(0);
        dummyHead -> next = head;
        ListNode* cur = dummyHead;
        int size = 0;

        while (cur -> next != nullptr) {
            cur = cur -> next;
            size++;
        }

        int index = size - n;

        cur = dummyHead;
        while (index--) {
            cur = cur -> next;
        }
        ListNode* tmp = cur -> next;
        cur -> next = cur -> next -> next;
        delete tmp;

        head = dummyHead -> next;
        delete dummyHead;

        return head;
    }
};

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

方法二： 双指针法

如果要删除倒数第$n$个节点，则让$fast$先移动$n$步，然后再让$fast$和$slow$同时移动，直到$fast$指向链表末尾，删除$slow$所指向的节点就行。

/**
 * 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* dummyHead = new ListNode(0);
        dummyHead -> next = head;
        ListNode* fast = dummyHead;
        ListNode* slow = dummyHead;

        while (n--) {
            fast = fast -> next;
        }

        while (fast -> next) {
            slow = slow -> next;
            fast = fast -> next;
        }

        ListNode* tmp = slow -> next;
        slow -> next = slow -> next -> next;
        delete tmp;

        head = dummyHead -> next;
        delete dummyHead;

        return head;
    }
};

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