LeetCode 19 删除链表的倒数第 N 个结点（快慢指针经典题）

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