[LeetCode]day13 19.删除链表的倒数第n个结点

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

题目描述

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

题解

解法一：使用两次遍历

思路

1.先通过一次遍历获得这个链表的长度size

2.通过size-n计算出移动到待删结点之前的结点数

3.再遍历使指针指向待删结点的前一个结点，

4.进行删除操作

自己先写：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head)return NULL;
        ListNode*p=head;
        int size=0;
        while(p){
            size++;
            p=p->next;
        }
        p=head;
        for(int i=0;i<size-n;i++){
                p=p->next;
        }
        ListNode*q=p->next;
        p->next=q->next;
        delete q;
        return head;
    }
};

修改答案：

报错：

报错来自于删除操作： p->next=q->next;

我们没有考虑到一种情况就是链表中要删的就是第一个节点

所以不存在移动到待删结点的前一个节点这种情况

所以我们可以加一个虚拟头结点，这样可以使操作统一

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head)return NULL;
       //添加虚拟头结点
        ListNode*dummy=new ListNode(0,head);
        //计算链表的大小
        ListNode*p=head;
        int size=0;
        while(p){
            p=p->next;
             size++;
        }
        //将结点移动到待删结点的前一个结点
        p=dummy;
        for(int i=0;i<size-n;i++){
                p=p->next;
        }
        //进行删除操作
        ListNode*q=p->next;
        p->next=q->next;
        delete q;
        return dummy->next;
    }
    
};

解法二：使用一次遍历

有没有方法可以实现只通过一次遍历，就能达到目的呢？

网上也有很多直接讲了快慢指针的方法但是没有讲解为什么这样做就行了

快慢指针的原理

我们假设链表的长度为size,待删元素为倒数第n个元素

我们采用两个指针，一个为快指针，一个为慢指针

快指针先移动n步即指向第n个元素然后快慢指针一起移动直到快指针指向最后一个元素

此时快指针移动了size-n个元素

慢指针此时就指向了第size-n个元素，即倒数第n个元素的前一个元素

举个例元素为1,2,3,4,5 n=2;

fast先移动两个元素的位置指向2 然后fast和slow一起移动直到fast指向最后一个元素 fast要移动三个元素 slow移动三个元素就是指向3 是倒数第二个元素前的一个元素

代码实现

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head)return NULL;
        ListNode*dummy=new ListNode(0,head);
        ListNode*fast=dummy,*slow=dummy;
        //fast移动n个元素
        for(int i=0;i<n;i++){
            fast=fast->next;
        }
        //fast和slow一起移动size-n个元素的位置
        while(fast->next!=NULL){
            fast=fast->next;
            slow=slow->next;
        }
        //此时slow指向倒数第n个元素的前一个位置 进行删除操作
        ListNode* temp=slow->next;
        slow->next=temp->next;
        delete temp;
        return dummy->next;
    }
    
};