- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
快慢指针
先明确，删除倒数第 n 个结点，我们需要找到倒数第 n+1 个结点，删除其后继结点即可。
1.添加 prev 哨兵结点，处理边界问题。
2.借助快慢指针，快指针先走 n+1 步，然后快慢指针同步往前走，直到 fast.next 为 null。
3.删除倒数第 n 个结点，返回 prev.next。
constremoveNthFromEnd=function(head,n){letprev=newListNode(0),fast=prev,slow=prev;prev.next=head;while(n--){fast=fast.next;}while(fast&&fast.next){fast=fast.next;slow=slow.next;}slow.next=slow.next.next;returnprev.next;}
- 时间复杂度：O(n)
- 空间复杂度：O(1)