前言

在本科毕设结束后，我开始刷卡哥的“代码随想录”，每天一节。自己的总结笔记均会放在“算法刷题-代码随想录”该专栏下。
代码随想录此题链接

题目

给你一个链表，删除链表的倒数第 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. 删除倒数链表(快慢指针法)

思路（定义变量）

1. 定义链表结构的结构体struct
2. 虚拟头节点 dummy。
3. 三个struct类型的指针，分别是fast,slow。

2. 本题思路分析：

1. fast,slow全部指向dummy虚拟头节点。
2. 将dummy的next指向head(易错点，特别容易遗忘)
3. fast指针先移动n个位置（n是要删除元素倒数的第n个的位置），然后fast、slow全部后移，直到fast挪到最后一个元素位置上（fast -> next != nullptr）。
4. 此时slow就在要删除节点的前一个节点上了，然后删除slow的下一个节点
5. 然后记得要将dummy的next指向head（易错点，容易漏），然后再将dummy删除。

3. 算法实现

• 代码：

#include
#include
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* removeNthFromEnd(ListNode* head, int n) {
		//一般涉及到删除节点，首先考虑使用到  虚拟头节点
		ListNode* dummy = new ListNode(0); 
		dummy -> next= head;//易错点,创建虚拟节点dummy后,老是漏掉把head放在它的next上(不要弄反或者忘记写了)
		ListNode* fast = dummy;
		ListNode* slow = dummy;
		while(n--){
			fast = fast -> next;
		}
		while(fast -> next != nullptr){
			fast = fast -> next;
			slow = slow -> next;
		}
		//现在slow在待删除节点的前一个位置 
		//删除节点 
		ListNode* tmp = slow -> next;
		slow -> next = slow -> next -> next;
		delete tmp;
		//易错点:老是漏掉这步,将head放在dummy的next,删除dummy节点
		head = dummy -> next;
		delete dummy; 
		return head;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

4. 算法分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

5. 算法坑点

1. dummy初始化后，记得将dummy->next指向head。
2. 删除指定元素后，记得在返回head前，将dummy->next赋值给head，并将dummy删除。