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