[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;
    }
    
};