LeetCode 19. Remove Nth Node From End of List 题解

LeetCode 19. Remove Nth Node From End of List 题解题目描述给你一个链表删除链表的倒数第n个结点并且返回链表的头结点。示例 1输入head [1,2,3,4,5], n 2 输出[1,2,3,5]示例 2输入head [1], n 1 输出[]示例 3输入head [1,2], n 1 输出[1]解题思路方法双指针思路使用两个指针fast和slow初始都指向哑节点先让fast指针移动n 1步然后同时移动fast和slow指针直到fast指针指向null此时slow指针指向的是倒数第n 1个节点将其下一个节点删除复杂度分析时间复杂度O(n)其中 n 是链表的长度。需要遍历链表一次。空间复杂度O(1)只需要常数级的额外空间。代码实现方法双指针# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]: # 创建哑节点方便处理头节点的情况 dummy ListNode(0) dummy.next head # 初始化快慢指针 fast dummy slow dummy # 先让 fast 指针移动 n 1 步 for _ in range(n 1): fast fast.next # 同时移动 fast 和 slow 指针直到 fast 指针指向 null while fast: fast fast.next slow slow.next # 删除倒数第 n 个节点 slow.next slow.next.next return dummy.next测试用例测试用例 1输入head [1,2,3,4,5], n 2输出[1,2,3,5]测试用例 2输入head [1], n 1输出[]测试用例 3输入head [1,2], n 1输出[1]总结本题是链表的经典问题主要考察对链表操作和双指针技巧的理解和应用。通过使用双指针我们可以高效地删除链表的倒数第 N 个节点。双指针的核心思想是先让快指针移动 N1 步然后同时移动快慢指针当快指针到达链表末尾时慢指针恰好指向倒数第 N1 个节点此时可以方便地删除倒数第 N 个节点。这种方法不仅适用于删除链表的倒数第 N 个节点问题还可以应用于许多其他需要定位链表中特定位置节点的场景。掌握双指针技巧对于解决链表问题非常重要。