19. Remove Nth Node From End of List
19. Remove Nth Node From End of List
题目
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. 交换链表中的节点](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)