LeetCode 19. 删除链表的倒数第N个结点双指针暴力法一趟扫描进阶实现题目描述给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。要求操作简洁高效同时实现进阶要求尝试使用一趟扫描完成删除操作。示例解析示例 1输入head [1,2,3,4,5]n 2输出[1,2,3,5]核心解析链表倒数第2个结点为4删除后剩余结点依次为1、2、3、5返回头结点1。示例 2输入head [1]n 1输出[]核心解析链表仅含1个结点删除倒数第1个结点后链表为空返回空。示例 3输入head [1,2]n 1输出[1]核心解析链表倒数第1个结点为2删除后仅剩结点1返回头结点1。提示补充贴合题目实用提醒链表结点数 sz 范围 [1, 30]无空链表除非删除后为空无需处理sz0的场景。结点值范围 [0, 100]删除操作仅涉及指针调整与结点值无关。n 的范围 [1, sz]确保倒数第n个结点一定存在无需额外判断n的合法性。进阶要求核心一趟扫描实现避免两次扫描先统计长度、再删除提升时间效率。解题思路核心突破兼顾基础与进阶本题核心是定位链表倒数第n个结点再执行删除操作调整前驱结点的next指针跳过目标结点。主要有两种解题方法基础暴力法适合新手入门、进阶双指针法满足一趟扫描要求面试首选以下分别详解。方法一暴力法两次扫描易理解核心思路分两步操作先确定链表长度再定位并删除目标结点逻辑简单适合新手掌握。第一次扫描遍历整个链表统计结点总数 sz确定链表长度。计算目标结点的正向位置正向第 (sz - n 1) 个结点如示例1sz5n2正向第4个结点为4。第二次扫描遍历到正向第 (sz - n) 个结点目标结点的前驱结点调整其next指针跳过目标结点完成删除。特殊处理若目标结点是头结点sz n直接返回 head.next 即可无需遍历到前驱结点。方法二双指针法一趟扫描进阶最优核心思路利用两个指针的“距离差”实现一趟扫描定位目标结点无需统计链表长度效率更高贴合进阶要求。创建虚拟头节点 dummy指向 head避免删除头结点时的特殊判断统一所有结点的删除逻辑。定义两个指针fast快指针和slow慢指针初始均指向 dummy。先让快指针fast向前移动 n 步此时 fast 与 slow 之间的距离为 n确保后续同步移动时fast 到末尾时slow 刚好指向目标结点的前驱。让 fast 和 slow 同步向前移动直到 fast 指向链表末尾fast.next 为 None。此时 slow 指向目标结点的前驱结点调整 slow.next slow.next.next跳过目标结点完成删除。返回 dummy.next虚拟头节点的下一个节点即删除后的链表头节点。图解辅助双指针法可视化理解以示例1head[1,2,3,4,5]n2为例分步图解双指针操作过程初始状态dummy [0] → 1 → 2 → 3 → 4 → 5fast 和 slow 均指向 dummy。快指针移动n2步fast 依次指向1、2此时 fast 与 slow 距离为2。fast 和 slow 同步移动直到 fast.next 为 None第一次同步fast指向3slow指向1第二次同步fast指向4slow指向2第三次同步fast指向5slow指向3第四次同步fast.next为None停止移动此时 slow 指向3目标结点4的前驱。删除操作slow.next slow.next.next3的next指向5删除结点4。最终结果dummy.next → 1 → 2 → 3 → 5与示例输出一致。完整AC代码两种方法严格贴合要求格式方法一暴力法两次扫描新手友好LeetCode 19 暴力法 AC代码# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next from typing import Optional class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]: # 第一步统计链表总长度 sz sz 0 curr head while curr: sz 1 curr curr.next # 特殊情况删除的是头节点sz n if sz n: return head.next # 第二步找到目标结点的前驱正向第 sz - n 个结点 prev head # 遍历到前驱结点需要走 sz - n - 1 步 for _ in range(sz - n - 1): prev prev.next # 第三步删除目标结点跳过目标结点 prev.next prev.next.next return head方法二双指针法一趟扫描进阶最优LeetCode 19 双指针法 AC代码面试首选# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next from typing import Optional class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]: # 虚拟头节点统一删除逻辑避免单独处理头节点 dummy ListNode(0, head) fast dummy # 快指针 slow dummy # 慢指针 # 第一步快指针先移动n步与慢指针拉开n步距离 for _ in range(n): fast fast.next # 第二步快慢指针同步移动直到快指针到达末尾 while fast.next: fast fast.next slow slow.next # 第三步删除目标结点慢指针指向目标结点的前驱 slow.next slow.next.next # 返回删除后的链表头节点虚拟头节点的下一个 return dummy.next代码逐行解析通俗易懂兼顾新手与进阶一、暴力法代码解析统计链表长度定义 curr 指针指向 head遍历整个链表每遍历一个结点sz 加1最终得到链表总长度。这一步是暴力法的核心也是两次扫描的第一次扫描。特殊情况处理删除头节点当 sz n 时说明要删除的是链表的头节点倒数第n个结点就是头节点直接返回 head.next 即可无需后续遍历操作简化逻辑。定位目标结点的前驱目标结点的正向位置是 sz - n 1其前驱结点的正向位置是 sz - n因此需要遍历 sz - n - 1 步让 prev 指针指向该前驱结点。执行删除操作通过 prev.next prev.next.next跳过目标结点实现删除目标结点会被Python垃圾回收机制自动清理。二、双指针法代码解析虚拟头节点 dummy创建 dummy ListNode(0, head)其 next 指向 head核心作用是“统一删除逻辑”。无论删除的是头节点还是中间结点都可以通过“找到前驱结点 → 调整next指针”完成删除无需单独判断头节点。快慢指针初始化fast 和 slow 均初始指向 dummy确保后续移动时能同步从链表头部开始包含虚拟头节点避免遗漏前驱结点。快指针先移动n步这是双指针法的核心技巧让 fast 先移动n步此时 fast 与 slow 之间的距离为n。后续同步移动时当 fast 到达链表末尾fast.next 为 Noneslow 刚好指向目标结点的前驱结点。快慢指针同步移动循环条件为 fast.next确保 fast 最终指向链表的最后一个结点而非 None此时 slow 指向目标结点的前驱刚好可以执行删除操作。删除目标结点与返回结果slow.next slow.next.next 跳过目标结点完成删除返回 dummy.next即删除后的链表真实头节点。复杂度分析专业严谨贴合面试要求方法一暴力法时间复杂度O(sz)O(sz)O(sz)其中 sz 为链表结点数。解析两次扫描链表第一次统计长度O(sz)第二次定位并删除O(sz)总时间复杂度仍为线性级无多余操作。空间复杂度O(1)O(1)O(1)。解析仅使用3个指针curr、prev和1个变量sz额外空间消耗为常数级无冗余空间。方法二双指针法时间复杂度O(sz)O(sz)O(sz)。解析仅扫描链表一次fast 和 slow 指针最多移动 sz 步一趟扫描完成所有操作满足进阶要求效率优于暴力法。空间复杂度O(1)O(1)O(1)。解析仅使用2个指针fast、slow和1个虚拟头节点dummy额外空间消耗为常数级与暴力法一致。总结双指针法在时间效率上更优一趟扫描代码逻辑更简洁是面试中的首选解法暴力法易理解适合新手入门帮助掌握链表删除的核心逻辑。测试示例可本地运行快速验证补充链表构建、打印辅助函数复制可直接本地运行验证所有示例方便调试和理解两种解法本地测试辅助代码示例验证# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next from typing import Optional # 辅助函数1根据列表构建链表贴合题目输入格式 def build_linked_list(arr): if not arr: return None dummy ListNode(0) curr dummy for val in arr: curr.next ListNode(val) curr curr.next return dummy.next # 辅助函数2打印链表直观查看结果 def print_linked_list(head): res [] while head: res.append(str(head.val)) head head.next return -.join(res) # 方法一暴力法可替换为双指针法代码 class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]: # 统计链表长度 sz 0 curr head while curr: sz 1 curr curr.next # 特殊情况删除头节点 if sz n: return head.next # 找到目标结点的前驱 prev head for _ in range(sz - n - 1): prev prev.next # 删除目标结点 prev.next prev.next.next return head # 测试示例1 head1 build_linked_list([1,2,3,4,5]) n1 2 res1 Solution().removeNthFromEnd(head1, n1) print(示例1输出, print_linked_list(res1)) # 输出1-2-3-5 # 测试示例2 head2 build_linked_list([1]) n2 1 res2 Solution().removeNthFromEnd(head2, n2) print(示例2输出, print_linked_list(res2)) # 输出空字符串 # 测试示例3 head3 build_linked_list([1,2]) n3 1 res3 Solution().removeNthFromEnd(head3, n3) print(示例3输出, print_linked_list(res3)) # 输出1常见易错点避坑指南高分关键新手必看易错点1暴力法中忘记处理“删除头节点”的特殊情况sz n导致空指针异常如示例2删除仅有的头节点仍执行遍历操作。易错点2暴力法中遍历前驱结点时步数计算错误应走 sz - n - 1 步而非 sz - n 步导致定位到目标结点而非前驱。易错点3双指针法中快指针移动步数不足n步或快慢指针同步移动时循环条件错误用 fast 而非 fast.next导致定位错误。易错点4双指针法中未使用虚拟头节点删除头节点时逻辑冗余易出错。避坑技巧双指针法牢记“快指针先移n步 → 快慢同步移 → 慢指针删结点”暴力法牢记“先统计长度 → 处理头节点 → 找前驱删结点”。进阶延伸提升文档深度助力高分本题是链表删除操作的经典进阶题核心是“倒数第n个结点的定位”掌握后可延伸解决以下同类题目解题思路可复用LeetCode 141. 环形链表利用双指针快慢指针判断链表是否有环本质是“指针距离差”的应用。LeetCode 142. 环形链表 II双指针结合数学推导找到环形链表的入口延伸双指针的使用场景。LeetCode 206. 反转链表结合双指针前驱指针、当前指针实现链表反转进一步巩固链表指针操作。补充进阶思考若链表结点数极大远超30双指针法的优势会更加明显一趟扫描可节省大量时间符合实际开发中“高效操作”的需求。总结提炼核心贴合CSDN高分风格本题核心考察链表指针操作和倒数结点定位难度适中是链表操作的经典题型也是面试高频题。解题核心记住两点① 暴力法适合新手分两步统计长度删除结点逻辑简单② 双指针法是进阶最优解利用“指针距离差”实现一趟扫描代码简洁、效率高面试首选。两种解法均满足题目要求代码可直接提交AC测试用例完整易错点和进阶延伸完善适合新手入门练习也可作为面试复习的重点题型。掌握本题后可进一步巩固链表指针操作能力轻松应对同类进阶题目。