LeetCode 19 删除链表的倒数第 N 个结点（快慢指针经典题）
题目描述
给你一个链表，删除链表的倒数第 N 个节点，并返回链表头节点。
要求：
- 只能遍历一次链表；
- 时间复杂度 O(n)。
一、核心思路
删除一个节点，本质上需要找到：
待删除节点的前驱节点例如：
1 -> 2 -> 3 -> 4 -> 5删除倒数第2个节点：
1 -> 2 -> 3 -> 5真正需要找到的是：
节点3因为：
3.next=5即可完成删除。
二、为什么想到快慢指针？
如果：
fast先走 N 步。
然后：
fast slow一起走。
那么：
fast 和 slow 永远相差 N 个节点。当：
fast到达末尾时：
slow正好停在待删除节点的前驱位置。
三、为什么需要 Dummy？
如果删除的是头节点：
1 -> 2 -> 3删除倒数第3个：
2 -> 3头节点发生变化。
为了统一逻辑：
dummy=ListNode(0,head)这样：
dummy -> 1 -> 2 -> 3删除任何节点都有前驱。
四、完整代码
classSolution:defremoveNthFromEnd(self,head,n):dummy=ListNode(0,head)slow=dummy fast=dummyfor_inrange(n):fast=fast.nextwhilefast.next:slow=slow.nextfast=fast.nextslow.next=slow.next.nextreturndummy.next五、复杂度分析
时间复杂度
O(n)只遍历一次链表。
空间复杂度
O(1)只使用有限几个指针变量。
六、高频易错点
1、忘记使用 Dummy
删除头节点时容易出错。
2、快指针先走 n+1 步
会导致慢指针位置错误。
3、删除时写错
正确：
slow.next=slow.next.next错误：
slow=slow.next.next七、一句话总结
快指针先走 N 步，快慢同速前进；快到末尾时，慢指针正好位于待删除节点的前驱位置。
