doocs/leetcode · LeetCode 19 删除链表的倒数第 N 个结点：快慢指针一趟扫描与虚拟头结点设计

示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本篇基于 doocs/leetcode 仓库中 LeetCode 19 题解文档系统讲解“删除链表倒数第 N 个结点”的完整题解从题目约束、一趟扫描的快慢指针设计到虚拟头结点如何统一“删头”与“删中间”两种分支。读完后你将掌握双指针定距推进的核心技巧并能对照仓库内 Python、Java、C、Go 等 10 种语言的实现细节与边界用例验证逻辑。题目描述与约束题目原文来自 README.md给你一个链表删除链表的倒数第n个结点并且返回链表的头结点。三个官方示例覆盖了三种典型形态示例输入输出考察点示例 1head [1,2,3,4,5], n 2[1,2,3,5]删除中间结点见上方示意图示例 2head [1], n 1[]单结点链表删除后链表为空示例 3head [1,2], n 1[1]删除尾结点约束条件提示部分链表中结点的数目为sz且1 sz 300 Node.val 1001 n szn一定有效无需判空保护。进阶要求你能尝试使用一趟扫描实现吗这正是本文题解的核心目标只遍历链表一次时间复杂度 $O(L)$并且不借助数组或栈额外存储结点。解题思路为什么“一趟扫描”要靠快慢指针原文档的思考过程给出了非常清晰的动机这里完整继承并展开朴素方案先遍历一遍得到链表长度 $L$再从头部走 $L - n$ 步定位到待删结点的前驱然后执行删除。时间复杂度 $O(L)$在sz 30的数据范围内当然可以接受但需要两趟遍历没有满足进阶要求。一趟扫描的难点不到链表末尾就无法确定“倒数第 $n$ 个”结点的绝对位置而单链表删除结点又必须拿到前驱结点不能拿到待删结点本身因为无法回头。快慢指针定距让快指针fast先走出 $n$ 步的间距再让fast、slow以相同速度前进。当fast到达表尾时slow恰好停在待删结点的前驱位置——间距 $n$ 被“平移”到了链表末端。虚拟头结点兜底若待删结点是头结点即n sz前驱不存在需要修改“返回头结点”本身。引入虚拟头结点dummy后删头结点与删中间结点共用同一套slow.next slow.next.next逻辑无需特判。从源码结构看Solution.py、Solution.java 等所有语言的实现都严格遵循这四步代码量极少核心逻辑仅 6~8 行这也是快慢指针方案的典型特征。算法走查以示例 1 为例逐步推演设链表为dummy → 1 → 2 → 3 → 4 → 5n 2指针初始都在dummy步骤操作fast 位置slow 位置初始化两指针均指向 dummydummydummy预走 n 步fast前进 2 步结点 2dummy同步前进 1fast.next非空结点 3结点 1同步前进 2fast.next非空结点 4结点 2同步前进 3fast.next非空结点 5表尾结点 3终止判断fast.next null退出循环结点 5结点 3循环结束后slow停在结点 3slow.next正是倒数第 2 个结点 4。执行slow.next slow.next.next把 4 从链表中摘除返回dummy.next即1 → 2 → 3 → 5与示例输出一致。这里有一个容易踩坑的细节同步循环的条件是fast.next ! null而不是fast ! null。因为预走 $n$ 步后fast与slow之间恰好间隔 $n$ 个结点若让fast走到“表尾之后”slow就会越过待删结点的前驱、直接停到待删结点上前驱信息丢失。维持“fast停在表尾结点”这一不变式slow.next才是前驱。所有语言的实现如 Solution.go 的for fast.Next ! nil、Solution.cpp 的while (fast-next)均统一采用这一终止条件从源码层面印证了该设计约定。完整实现仓库内 10 种语言以下代码完整取自 README.md 的解法区块并与仓库中对应的独立源文件Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.swift、Solution.rb、Solution.cs、Solution.php保持一致。Python3# 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(nexthead) # 虚拟头结点统一删除头结点的分支 fast slow dummy for _ in range(n): # fast 先走 n 步建立定距间距 fast fast.next while fast.next: # fast 停在表尾结点时退出 slow, fast slow.next, fast.next slow.next slow.next.next # 摘除倒数第 n 个结点 return dummy.nextJava/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0, head); ListNode fast dummy, slow dummy; while (n-- 0) { fast fast.next; } while (fast.next ! null) { slow slow.next; fast fast.next; } slow.next slow.next.next; return dummy.next; } }C/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0, head); ListNode* fast dummy; ListNode* slow dummy; while (n--) { fast fast-next; } while (fast-next) { slow slow-next; fast fast-next; } slow-next slow-next-next; return dummy-next; } };Go/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func removeNthFromEnd(head *ListNode, n int) *ListNode { dummy : ListNode{0, head} fast, slow : dummy, dummy for ; n 0; n-- { fast fast.Next } for fast.Next ! nil { slow, fast slow.Next, fast.Next } slow.Next slow.Next.Next return dummy.Next }TypeScript/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val (valundefined ? 0 : val) * this.next (nextundefined ? null : next) * } * } */ function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null { const dummy new ListNode(0, head); let fast dummy; let slow dummy; while (n--) { fast fast.next; } while (fast.next) { slow slow.next; fast fast.next; } slow.next slow.next.next; return dummy.next; }Rust// Definition for singly-linked list. // #[derive(PartialEq, Eq, Clone, Debug)] // pub struct ListNode { // pub val: i32, // pub next: OptionBoxListNode // } // // impl ListNode { // #[inline] // fn new(val: i32) - Self { // ListNode { // next: None, // val // } // } // } impl Solution { pub fn remove_nth_from_end(head: OptionBoxListNode, n: i32) - OptionBoxListNode { let mut dummy Some(Box::new(ListNode { val: 0, next: head })); let mut slow mut dummy; let mut fast slow.clone(); for _ in 0..n { fast fast.as_ref().unwrap().next; } while fast.is_some() { fast fast.as_ref().unwrap().next; slow mut slow.as_mut().unwrap().next; } slow.as_mut().unwrap().next slow.as_mut().unwrap().next.as_mut().unwrap().next.take(); dummy.unwrap().next } }Rust 版本通过OptionBoxListNode表达空指针语义需要显式unwrap()与take()操作注意其循环条件写法与指针推进方式与其他语言等价只是所有权模型的体现。JavaScript/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val (valundefined ? 0 : val) * this.next (nextundefined ? null : next) * } */ /** * param {ListNode} head * param {number} n * return {ListNode} */ var removeNthFromEnd function (head, n) { const dummy new ListNode(0, head); let fast dummy, slow dummy; while (n--) { fast fast.next; } while (fast.next) { slow slow.next; fast fast.next; } slow.next slow.next.next; return dummy.next; };Swift/** * Definition for singly-linked list. * public class ListNode { * public var val: Int * public var next: ListNode? * public init() { self.val 0; self.next nil; } * public init(_ val: Int) { self.val val; self.next nil; } * public init(_ val: Int, _ next: ListNode?) { self.val val; self.next next; } * } */ class Solution { func removeNthFromEnd(_ head: ListNode?, _ n: Int) - ListNode? { let dummy ListNode(0) dummy.next head var fast: ListNode? dummy var slow: ListNode? dummy for _ in 0..n { fast fast?.next } while fast?.next ! nil { fast fast?.next slow slow?.next } slow?.next slow?.next?.next return dummy.next } }Swift 用可选链fast?.next ! nil表达“fast非空且其next非空”的复合终止条件。Ruby# Definition for singly-linked list. # class ListNode # attr_accessor :val, :next # def initialize(val 0, _next nil) # val val # next _next # end # end # param {ListNode} head # param {Integer} n # return {ListNode} def remove_nth_from_end(head, n) dummy ListNode.new(0, head) fast slow dummy while n 0 fast fast.next n - 1 end while fast.next slow slow.next fast fast.next end slow.next slow.next.next return dummy.next endC#/** * Definition for singly-linked list. * public class ListNode { * public int Val; * public ListNode Next; * public ListNode(int val0, ListNode nextnull) { * this.val val; * this.next next; * } * } */ public class Solution { public ListNode RemoveNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0, head); ListNode fast dummy, slow dummy; while (n-- 0) { fast fast.next; } while (fast.next ! null) { slow slow.next; fast fast.next; } slow.next slow.next.next; return dummy.next; } }PHP仓库 README 中还提供了 PHP 版本与 Solution.php 对应class Solution { /** * param ListNode $head * param Integer $n * return ListNode */ function removeNthFromEnd($head, $n) { $dummy new ListNode(0, $head); $fast $slow $dummy; for ($i 0; $i $n; $i) { $fast $fast-next; } while ($fast-next ! null) { $fast $fast-next; $slow $slow-next; } $slow-next $slow-next-next; return $dummy-next; } }各语言实现的关键差异仅在于空值表达方式null/None/nil/可选类型算法骨架完全一致建虚拟头 → 快指针预走 $n$ 步 → 双指针同步至fast.next为空 → 摘除slow.next→ 返回dummy.next。复杂度分析时间复杂度$O(L)$其中 $L$ 为链表长度快指针预走 $n$ 步 同步推进至表尾链表总访问次数不超过一趟量级空间复杂度$O(1)$仅使用dummy、fast、slow三个指针/结点未分配与 $L$ 相关的额外结构。这比“两次遍历”的朴素方案同样 $O(L)$ 时间更少一次完整扫描且与“数组记录全部结点”的 $O(L)$ 空间方案相比额外空间从 $O(L)$ 降到了 $O(1)$完整满足进阶要求。边界用例验证约束1 n sz保证了n有效但仍有三个值得逐一推演的边界删除头结点n sz例如head [1,2]、n 2。fast预走 2 步直接到达表尾结点 2fast.next null同步循环一次都不执行slow仍停在dummyslow.next即头结点 1删除后返回dummy.next为结点 2。这正是虚拟头结点存在的意义——若直接操作原head此情形需要单独特判。单结点链表示例 2head [1]、n 1。fast预走 1 步到达表尾结点 1同步循环不执行删除slow.next后dummy.next为空返回空链表与预期输出[]一致。删除尾结点示例 3head [1,2]、n 1。fast预走 1 步到达结点 1同步 1 步后fast停在表尾结点 2、slow停在结点 1删除slow.next得到[1]。这三个用例恰好覆盖了“删头、删空、删尾”三类拓扑变化可作为自测时的最小测试集。延伸阅读英文题解README_EN.md各语言独立源文件均位于 solution/0000-0099/0019.Remove Nth Node From End of List/ 目录下Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.swift、Solution.rb、Solution.cs、Solution.php本仓库以“题目录 多语言 Solution 文件 图文题解”组织 LeetCode 题解同目录下可参考其他链表题的同类结构继续深入。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LeetCode 19. 删除链表的倒数第 N 个结点doocs/leetcode 快慢指针一趟扫描多语言题解LeetCode 19. 删除链表的倒数第 N 个结点doocs/leetcode 快慢指针一趟扫描多语言题解 本文基于 doocs/leetcode 开源仓示例工程leetcode 题解19. 删除链表的倒数第 N 个节点 —— 双指针 虚拟头一次遍历详解leetcode 题解19. 删除链表的倒数第 N 个节点 —— 双指针 虚拟头一次遍历详解 本文以本仓库的 19.removeNthNodeFromEn文档教程知识库基于 Decart Lucy 实时视频重绘构建语音驱动虚拟试衣智能体decart_example 深度解析基于 Decart Lucy 实时视频重绘构建语音驱动虚拟试衣智能体decart_example 深度解析 本文基于 Vision Agents 开源仓库 pAgent 框架音视频计算机视觉上一篇react-admin useRecordFromLocation 深度解析从 Location 预填 Create/Edit 表单字段下一篇用 Ragas CLI 评估数学解题 Agentagent_evals 模板实战与源码解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考