LeetCode 热题 100_删除链表的倒数第 N 个结点（29_19_中等_C++）(单链表；双指针)（new_delete）

LeetCode 热题 100_删除链表的倒数第 N 个结点（29_19）

- 题目描述：
- 输入输出样例：
- 题解：
- - 解题思路：
  - - 思路一（计算链表长度）：
    - 思路二（双指针）：
  - 代码实现
  - - 代码实现（思路一（计算链表长度））：
    - 代码实现（思路二（双指针））：
    - 以思路二为例进行调试：
    - 部分代码解读

题目描述：

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

提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

题解：

解题思路：

思路一（计算链表长度）：

1、先求出链表的长度，再定位其前驱结点将对应结点删除。（注意头结点的删除和其他结点不同，因没有前驱结点。）
2、复杂度分析：
① 时间复杂度：O(L)，其中 L 是链表的长度。
② 空间复杂度：O(1)。

思路二（双指针）：

1、使用两个指针，控制距离为n+1。当后边的指针遍历到NULL时，前边的指针正好指向要删除结点的前驱。（为了统一各个结点的删除操作，这里我们对链表添加一个新头结点（dummyHead），体会和方法一中的不同）。

2、具体思路如下：
① 添加一个新头结点（dummyHead）。
② 先将一个指针tail从链表头结点（dummyHead）开始移动n+1步。再令结点pre指向头节点（dummyHead）。
③ 这时tail和pre同时移动，当tail到达尾结点时，pre正好是倒数第 n 个结点的前去结点。

3、复杂度分析
① 时间复杂度：O(L)，其中 L 是链表的长度。
② 空间复杂度：O(1)。

代码实现

代码实现（思路一（计算链表长度））：

ListNode* removeNthFromEnd1(ListNode* head, int n) {ListNode *p=head;int len=0;//统计链表长度 while(p!=nullptr){++len;p=p->next;}//删除结点为头结点的情况 if(len==n){p=head;head=head->next;delete p;return head;}//删除结点不是头结点的情况，先找到前驱结点p=head;for(int i=1;i<=len-n-1;++i){p=p->next;	}//删除结点 ListNode *tmp=p->next;p->next=p->next->next;//注意将结点释放delete tmp;return head;
}

代码实现（思路二（双指针））：

ListNode* removeNthFromEnd2(ListNode* head, int n) {//为了方便统一删除操作，这里我们对链表添加一个新头结点（dummyHead）ListNode *dummyHead=new ListNode(0,head); //pre记录删除结点的前驱结点，tail用于控制距离 ListNode *pre=dummyHead,*tail=dummyHead;//tail拉开n+1的距离 while(n+1){tail=tail->next;--n;} //tail和pre保持n+1个距离移动 while(tail!=nullptr){tail=tail->next;pre=pre->next;}//删除结点（用tail来存储需删除的结点节省内存空间） tail=pre->next;pre->next=pre->next->next;head=dummyHead->next;delete dummyHead;//注意返回头节点之后的结点 return head;
}

以思路二为例进行调试：

#include<iostream> 
#include<vector>
using namespace std;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){}
};//尾插法创建单链表 
ListNode *createList(vector<int> arr){ListNode *head=nullptr,*tail=nullptr;for(const auto &val:arr){if(head==nullptr){tail=head=new ListNode(val);}else{tail->next=new ListNode(val);tail=tail->next;}}return head;
}//方法二
ListNode* removeNthFromEnd2(ListNode* head, int n) {//为了方便统一删除操作，这里我们对链表添加一个新头结点（dummyHead）ListNode *dummyHead=new ListNode(0,head); //pre记录删除结点的前驱结点，tail用于控制距离 ListNode *pre=dummyHead,*tail=dummyHead;//tail拉开n+1的距离 while(n+1){tail=tail->next;--n;} //tail和pre保持n+1个距离移动 while(tail!=nullptr){tail=tail->next;pre=pre->next;}//删除结点（用tail来存储需删除的结点节省内存空间） tail=pre->next;pre->next=pre->next->next;head=dummyHead->next;delete dummyHead;//注意返回头节点之后的结点 return head;
}int main(){vector<int> a={1,2,3,4,5};int n=2;//创建单链表ListNode *head=createList(a);//删除链表的倒数第 N 个结点ListNode *ans=removeNthFromEnd2(head,n);//输出删除后的单链表while(ans!=nullptr){cout<<ans->val<<"->";ans=ans->next;}cout<<"null"; return 0;
}