豆包 LeetCode 19. 删除链表的倒数第 N 个结点 Python3实现

LeetCode 19 删除链表的倒数第 N 个结点 Python3题意给链表头节点删除倒数第 n 个节点返回链表头。最优思路快慢指针双指针快指针先走n步之后快慢一起走快到末尾时慢指针指向待删节点前驱。pythonDefinition for singly‑linked list.class ListNode:definit(self, val0, nextNone):self.val valself.next nextclass Solution:def removeNthFromEnd(self, head: ListNode, n: int) - ListNode:# 虚拟头节点处理要删除头节点的边界dummy ListNode(0, head)fast dummyslow dummy# fast先走n步 for _ in range(n): fast fast.next # fast走到链表末尾 while fast.next is not None: fast fast.next slow slow.next # 删除slow的下一个节点 slow.next slow.next.next return dummy.next复杂度时间复杂度O(L)L链表长度仅遍历一次链表空间复杂度O(1)只使用常数指针无额外数组关键细节使用dummy虚拟头结点统一处理删除头结点的特殊情况不需要单独判断快指针先走n步再同步移动slow最终定位到待删除节点的前一个节点不计算链表长度一趟遍历完成补充如果需要我可以给先求链表长度的两趟遍历版本。