19. Remove Nth Node From End of List

🟠   🔖  链表 双指针  🔗 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 的位置，删除该位置上的节点；
  • 需要注意的一个特例是，有可能要删除头节点，在遍历之前，新建一个头节点，让其指向原来的头节点。

• 思路二：快慢指针

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

代码

/**
 * @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;
};

相关题目

相关题目

• 1721. 交换链表中的节点
• 🔒 Delete N Nodes After M Nodes of a Linked List
• 2095. 删除链表的中间节点

- [1721. 交换链表中的节点](https://leetcode.com/problems/swapping-nodes-in-a-linked-list)
- [🔒 Delete N Nodes After M Nodes of a Linked List](https://leetcode.com/problems/delete-n-nodes-after-m-nodes-of-a-linked-list)
- [2095. 删除链表的中间节点](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list)