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

题目

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

示例：

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

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

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

解答 & 代码

快慢指针：快指针先走 N 步，然后两个一起走，快指针走到 nullptr 时慢指针恰好走到倒数第 N 个节点。又因为题目是要删除倒数第 N 个节点，所以应该定位到倒数第 N + 1 个节点。快指针走到 fast->next == nullptr 时，慢指针恰好走到倒数第 N + 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) {
        ListNode* dummyHead = new ListNode(-1, head);    // 虚拟头节点
        ListNode* fast = dummyHead;                        // 快指针
        ListNode* slow = dummyHead;                        // 慢指针
        // 快指针先走 n 步
        int i = 0;
        while(fast != nullptr && i < n)
        {
            fast = fast->next;
            ++i;
        }
        // 如果 i < n，说明链表长度小于 n，不用删除，直接返回头节点
        if(i < n)
            return dummyHead->next;
        // 快慢指针同时走，最终将 slow 定位到倒数第 N+1 个节点
        while(fast->next != nullptr)
        {
            fast = fast->next;
            slow = slow->next;
        }
        // 删除倒数第 N 个节点
        ListNode* deleteNode = slow->next;
        slow->next = slow->next->next;
        delete deleteNode;
        return dummyHead->next;
    }
};

复杂度分析：设链表共 M 个节点

• 时间复杂度 O(M)
• 空间复杂度 O(1)

执行结果：

执行结果：通过
执行用时：4 ms, 在所有 C++ 提交中击败了 77.40% 的用户
内存消耗：10.3 MB, 在所有 C++ 提交中击败了 93.54% 的用户

换种写法：

/**
 * 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 {
private:
    // 返回倒数第 n 个节点
    ListNode* NthFromEnd(ListNode* head, int n)
    {
        ListNode* fast = head;    // 快指针
        ListNode* slow = head;    // 慢指针
        // 快指针先走 n 步
        int i = 0;
        for(; i < n && fast != nullptr; ++i)
            fast = fast->next;
        if(i < n)    // 链表长度 < n，不存在倒数第 n 个节点，返回 nullptr
            return nullptr;
        // 快慢指针同时走
        while(fast != nullptr)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;    // 返回倒数第 n 个节点
    }
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(-1, head);    // 虚拟头节点
        // 先定位到倒数第 N+1 个节点
        ListNode* lastN1thNode = NthFromEnd(dummyHead, n + 1);
        // 删除倒数第 N 个节点
        if(lastN1thNode != nullptr)
        {
            ListNode* deleteNode = lastN1thNode->next;
            lastN1thNode->next = lastN1thNode->next->next;
            delete deleteNode;
        }
        return dummyHead->next;
    }
};