LeetCode算法笔记–Day33
19. Remove Nth Node From End of List
题目：
Given a linked list, remove the n-th node from the end of list and return its head.
example
input: 1->2->3->4->5, and n = 2.
output: 1->2->3->5.
My Answer：
双指针
时间复杂度：O(n)
空间复杂度：O(1)
设快慢两个指针
1、快指针先移n个节点
2、快、慢指针一起移动，使得两指针之间一直保持n个节点
3、当指针到达链表底了，将慢指针的指针指向它的下下一个指针
4、慢指针的下一个指针即为要删除的节点边界
最后返回哨兵节点的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
25
26
27
28
| /**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
let preHead = new ListNode(-1);
preHead.next = head;
let left = preHead;
let right = preHead;
while(n != 0){
right = right.next;
n--;
}
while(right.next != null){
right = right.next;
left = left.next;
}
left.next = left.next.next;
return preHead.next;
};
|
