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

🟠   🔖  链表 双指针  🔗 力扣 LeetCode

题目

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2

Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1

Output: []

Example 3:

Input: head = [1,2], n = 1

Output: [1]

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Follow up: Could you do this in one pass?

题目大意

删除链表中倒数第 n 个结点。

解题思路

思路一：单指针

• 先遍历一遍链表，统计一下节点个数为 len，再遍历到 len - n 的位置，删除该位置上的节点；
• 需要注意的一个特例是，有可能要删除头节点，在遍历之前，新建一个头节点，让其指向原来的头节点。

复杂度分析

• 时间复杂度：O(L)，其中 L 是链表的长度。
  • 首先遍历链表一次来计算链表的长度 L，这需要 O(L) 的时间。
  • 再次遍历链表，移动指针到需要删除的节点的前一个节点，所需的时间也是 O(L)。
  • 因此，总时间复杂度为 O(L)。
• 空间复杂度：O(1)，只使用了常数空间来存储指针和变量。

---

思路二：快慢指针

• 使用两个指针 slow、fast，都指向链表的头节点;
• 让快指针 fast 先走 n 步；
• 再让快慢指针同时走，每次一步，等快指针遍历到链表尾部的时候，慢指针就刚好遍历到了倒数第 n 个节点位置；
• 将该位置上的节点删除即可。

复杂度分析

• 时间复杂度：O(L)，其中 L 是链表的长度。
  • 首先将快指针 fast 向前移动 n 步，这需要 O(n) 的时间。
  • 然后同时移动快指针和慢指针 slow，直到快指针到达链表末尾。该操作遍历了链表的剩余部分，最多需要 O(L - n) 的时间。
  • 因此，总的时间复杂度仍为 O(L)。
• 空间复杂度：O(1)，只使用了常数空间来存储指针和变量。

代码

单指针

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
	let res = new ListNode(0, head),
		len = 0,
		p = res;
	while (head) {
		head = head.next;
		len++;
	}
	for (let i = 0; i < len - n; i++) {
		p = p.next;
	}
	p.next = p.next.next;
	return res.next;
};

快慢指针

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
	let res = new ListNode(0, head);
	let slow = res;
	let fast = head;
	while (n) {
		fast = fast.next;
		n--;
	}
	while (fast) {
		slow = slow.next;
		fast = fast.next;
	}
	slow.next = slow.next.next;
	return res.next;
};

相关题目

题号	标题	题解	标签	难度	力扣
1474	删除链表 M 个节点之后的 N 个节点 🔒		链表	🟢	🀄️ 🔗
1721	交换链表中的节点		链表 双指针	🟠	🀄️ 🔗
2095	删除链表的中间节点	[✓]	链表 双指针	🟠	🀄️ 🔗