126.删除链表的倒数第N个节点（力扣）

题目描述

代码解决（双指针）

/**
 * 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!=nullptr)
        {
            fast=fast->next;
        }
        fast=fast->next;
        while(fast!=nullptr)
        {
            fast=fast->next;
            slow=slow->next;
        }
        slow->next=slow->next->next;

        return dummyHead->next;
    }

};

这段代码是一个用于删除单向链表中倒数第n个节点的函数。让我们逐行来解释一下：

1. ListNode是一个单向链表节点的结构体或类，假设它有一个整型的val成员和一个指向下一个节点的指针next。

2. class Solution定义了一个类，其中包含了公有的成员函数removeNthFromEnd，该函数接收一个指向链表头部的指针head和一个整数n，表示要删除倒数第几个节点。

3. ListNode*dummyHead=new ListNode(0);创建了一个值为0的虚拟头节点dummyHead，这样做是为了方便处理边界情况，避免单独处理头节点的删除情况。

4. dummyHead->next=head;将虚拟头节点的next指针指向实际的链表头节点head，这样做是为了保持链表的结构。

5. ListNode*fast=dummyHead;和ListNode*slow=dummyHead;创建了两个指针fast和slow，初始都指向虚拟头节点，用来找到要删除的节点位置。

6. while(n--&&fast!=nullptr)是一个循环，条件是n不为0且fast不为空。循环内部让fast指针往前移动，相当于让fast指针领先slow指针n个节点。

7. fast=fast->next;在上面的循环结束后，再额外往前移动一步，以便让fast指向要删除节点的前一个节点，这样才能正确删除节点。

8. 接下来是第二个循环while(fast!=nullptr)，在这个循环中，fast和slow指针一起往前移动，直到fast指向链表末尾的nullptr。

9. slow->next=slow->next->next;这一行代码实际上删除了倒数第n个节点。它将slow指针的next指针直接指向了要删除节点的下一个节点，跳过了要删除的节点。

10. 最后，return dummyHead->next;返回删除节点后的链表头节点，即实际链表的头节点。

这段代码利用了快慢指针的方法，在一次遍历中完成了删除倒数第n个节点的操作，时间复杂度为O(N)，其中N是链表的长度。