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

题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

将删除倒数第n个节点转化为删除第n个节点

  先用一个哑节点（虚拟头节点）来简化删除头节点的情况。然后，它通过第一次遍历计算出链表的长度，接着计算出要到达的节点，最后通过第二次遍历找到目标节点的前一个节点。通过修改指针，实现了目标节点的删除，并且在结束前释放了删除节点和哑节点占用的内存。最终返回了新链表的头节点。
  删除第n个节点时需要找到前一个节点才能删除

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyhead = new ListNode(0); // 创建一个哑节点，其值为0，next指向链表的头节点head
        dummyhead->next = head;
        ListNode* cur = dummyhead; // 创建一个指针cur，初始化为指向哑节点
        int size = 0;
        while(cur) { // 遍历整个链表来计算链表的长度
            cur = cur->next;
            size++;
        }
        cur = dummyhead; // 重置cur指针回到哑节点的位置，准备第二次遍历
        int a = size - n - 1; // 计算正向第size-n个节点的索引（因为哑节点的存在，所以要额外减1）

        while(a--) { // 移动cur指针到正向第size-n个节点的前一个节点上
            cur = cur->next;
        }
        ListNode* tmp = cur->next; // 创建一个临时指针tmp，指向要删除的节点
        cur->next = cur->next->next; // 将要删除节点的前一个节点的next指向要删除节点的下一个节点，从而断开连接

        delete tmp; // 删除tmp指针指向的节点，释放内存

        ListNode* newHead = dummyhead->next; // 保存新的头节点，即哑节点的下一个节点
        delete dummyhead; // 删除哑节点，释放内存
        
        return newHead; // 返回新的头节点
    }
};

双指针

  通过使用两个指针来实现的，一个快指针（fast）首先向前移动 n 步，然后快指针和慢指针（slow）一起移动直到快指针到达链表尾部。此时慢指针指向的是倒数第 n 个节点的前一个节点。然后该节点被删除，并释放其内存。最后，函数删除了在开始时创建的哑节点（虚拟头节点），并返回链表的新头节点。

• fast先移动n步
  
• 然后fast和slow再同时移动，fast移动到NULL，slow随着fast一起移动就能找到需要删除的节点，因为删除节点需要找到删除节点的前一个结点，所以fast只需要移动到NULL的前一个结点，slow结点也就移动到删除节点的前一个结点
  

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 创建一个哑节点（dummy head），其值不重要，目的是为了简化边缘情况的处理，
        // 比如删除的是链表的头节点。哑节点的下一个节点是链表的实际头节点。
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;

        // 创建两个指针，fast 和 slow，都开始时指向哑节点
        ListNode* fast = dummyhead;
        ListNode* slow = dummyhead;

        // 移动快指针fast，使其领先慢指针slow n 个节点。
        // 这是为了当fast指针到达链表末尾时，slow指针将指向倒数第n个节点的前一个节点。
        while(n--)
            fast = fast->next;

        // 同时移动快指针和慢指针，直到快指针到达最后一个节点。
        // 这样做是为了找到倒数第n个节点，因为当快指针到达链表尾部时，
        // 慢指针将会指向倒数第n个节点前的一个节点。
        while(fast->next != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }

        // slow指针现在指向倒数第n个节点的前一个节点，
        // tmp是倒数第n个节点，准备删除这个节点。
        ListNode* tmp = slow->next;

        // 断开倒数第n个节点的连接，将其前一个节点的next指向其下一个节点，
        // 从而将其从链表中移除。
        slow->next = slow->next->next;

        // 删除tmp指针指向的节点，即释放倒数第n个节点的内存。
        delete tmp;
        // 将tmp设置为nullptr，防止悬挂指针导致的未定义行为。
        tmp = nullptr;

        // newhead是指向链表新头节点的指针，即哑节点之后的节点。
        ListNode* newhead = dummyhead->next;

        // 删除哑节点，释放其内存。
        delete dummyhead;
        // 将dummyhead设置为nullptr，防止悬挂指针导致的未定义行为。
        dummyhead = nullptr;

        // 返回链表的新头节点。
        return newhead;
    }
};