Open Cosen95 opened 4 years ago
分析题目,题干有两个关键点:
删除
倒数第N个节点
对应删除
操作。我们一般是需要找到被删除节点的前驱节点
。而删除操作一般会用到dummy
结点。
这道题目中提到了
dummy
结点:它可以帮我们处理掉头结点为空的边界问题,帮助我们简化解题过程。const dummy = new ListNode() // 这里的 head 是链表原有的第一个结点 dummy.next = head
链表的删除没有什么难度(改变要被删除节点的前驱节点的
next
指向即可)。这道题的难点实际在于这个倒数第 N 个
如何定位。
我们正常遍历时不太可能从后往前走,因此这个倒数第 N 个”
完全可以转换为正数第 len - n + 1
个。
定位这个节点,我们需要两次遍历:‘
len
len-n+1
)的前驱节点(len-n
)到这里,答案已经呼之欲出了。
不过,等等,还有更好的解决方法吗?
其实,我们可以用快慢指针
来解决:
slow
和 fast
,全部指向链表的起始位——dummy
结点;n
步,在第 n
个结点处停住;n
个结点的前一个结点;/**
* 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) {
const dummy = new ListNode();
dummy.next = head;
let fast = dummy,
slow = dummy;
while(n !== 0) {
fast = fast.next;
n--
}
while(fast.next) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
};
leetcode: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/