代码随想录二刷 ｜ 链表 ｜ 删除链表的倒数第N个节点

题目描述

19.删除链表的倒数第N个节点

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

进阶：你能尝试使用一趟扫描实现吗？

解题思路 & 代码实现

双指针法

设置两个指针：fast和slow，fast指针先移动 n 步，然后fast指针和slow指针同时移动，直到fast指针指向链表末尾，最后删掉slow指向的元素即可。

class Solution{
public:
	ListNode* removeNthFromEnd(ListNode* head, int n) {
		ListNode* dummyHead = new ListNode(0);
		dummyHead -> next = head;
		ListNode* slow = dummyHead;
		ListNode* fast = dummyHead;
		// fast指针移动 n 步
		while (n-- && fast != NULL){
			fast = fast -> next;
		}
		// fast指针再移动一步，因为设置了虚拟头节点
		fast = fast -> next;
		// fast 、slow同时移动，fast移动到末尾时，slow移动到了倒数第 n 个位置
		while (fast != NULL) {
			fast = fast -> next;
			slow = slow -> next;
		}
		// 删除slow指向的元素
		slow -> next = slow -> next -> next;
		// 返回头节点
		return  dummyHead - > next;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24