526互联

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

发布时间 2023-10-27 16:25:55作者: DawnTraveler

1.题目介绍

给你一个链表，删除链表的倒数第 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]

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

2.题解（快慢指针）

2.1 初始代码

思路

这里的思路很简单，使用快慢指针的思想。这里注意，我要删除倒数第n个节点，应该要找到它的前一个节点才能顺利删除！
这里经过观察可以发现，当快指针快于慢指针n个节点时，当快指针指向结尾节点，慢指针指向的正是我们所要删除目标节点的前一个节点（涉及简单的种树问题）
所以我们正要使快指针先跑n个节点，再使快慢指针一起跑，最后进行删除操作即可。

但是这里又有一个问题，快指针起始指向的head指针指向第一个节点，当我们要删除第一个节点的时候，它向后跑n个节点直接跑到了nullptr，
而我们这里的判断 while (fast->next != nullptr) 就会发生空指针指向的报错！
在这里我最开始是将其单独列出讨论的，但是后面发现了更简单的写法（虚拟头结点），见2.2

代码

//
// Created by trmbh on 2023-10-27.
//19. 删除链表的倒数第 N 个结点

#include<iostream>

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 *fast = head, *slow = head, *temp = nullptr;
        if (head == nullptr) return head;

        // fast领先slow指针n个节点，最终使slow定位到待删除节点的（前一个节点，便于删除节点）
        for (int i = 0; i < n; i++) {
            if (fast -> next == nullptr) //说明删除的是第一个节点
            {
                temp = head;
                head = head -> next;
                delete temp;
                return head;
            }
            fast = fast->next;
        }

        // 快慢指针开始移动
        while (fast->next != nullptr){
            fast = fast -> next;
            slow = slow -> next;
        }

        // 节点删除操作
        temp = slow->next;
        slow -> next = temp -> next;
        delete temp;
        return head;
    }
};

int main(){
    ListNode node(2);
    ListNode head(1, &node);
    int n = 2;
    Solution solution;
    ListNode* p = &head;
    p = solution.removeNthFromEnd(p, n);
    while (p != nullptr){
        std::cout << p->val << ' ';
        p = p->next;
    }
}

2.2 代码优化

前面说了的问题，我想要快指针快于慢指针n个节点。但实际操作时，当我们要删除第一个节点的时候，会发生空指针指向的问题。
当然我们可以设置一个pre指针，始终指向慢指针的前一个指针，然后快指针快于慢指针n-1个节点（最后指向删除节点），这样最后也能实现目标，但要同时保管三个指针，且pre指针有很多重复的赋值操作。

我们再思考一下，这里我只需要快指针快于慢指针n个节点，并没有要求二者从哪开始运动，我这里如果再添加一个虚拟头结点作为二者的起点，那么即使是最极端情况删除第一个节点的时候，最后快指针也只会指向尾结点，而不会指向nullptr！

class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode dummy(0); // 使用虚拟头节点，避免特殊处理
        dummy.next = head;
        ListNode *fast = &dummy, *slow = &dummy;

        // 将 fast 领先 slow 指针 n 个节点，使得 slow 指针指向待删除节点的前一个节点
        for (int i = 0; i < n; i++) {
            fast = fast->next;
        }

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

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

        return dummy.next; // 返回链表的头节点
    }
};