示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文以开源仓库 doocs/leetcode 中 lcci/02.01.Remove Duplicate Node/README_EN.md 为核心骨架讲解《程序员面试金典第 6 版》面试题 02.01「移除未排序链表中的重复节点」的完整解法。文章覆盖题目约束、哈希表单次遍历去重的核心思路、时间/空间复杂度分析以及 Python3、Java、C、Go、TypeScript、Rust、JavaScript、Swift 共 8 种语言的实现细节并回答文档提出的进阶问题不使用临时缓冲区时如何求解。读完本文你将掌握「虚拟头节点 哈希表」这一链表删除类问题的通用套路并能直接复用仓库中已验证的源码。题目描述编写代码移除未排序链表中的重复节点并保留最开始出现的节点。示例 1输入[1, 2, 3, 3, 2, 1]输出[1, 2, 3]示例 2输入[1, 1, 1, 1, 2]输出[1, 2]提示与约束详见 英文题解 与 中文题解链表长度在[0, 20000]范围内链表可以为空即head null链表元素的值在[0, 20000]范围内元素非负可直接作为哈希键使用。进阶问题如果不得使用临时缓冲区该如何解决该问题在文末给出分析与解答。解题思路哈希表 虚拟头节点单次遍历去重核心思路推导去重的本质是判定「某个值是否已经出现过」。原始最朴素的做法是对每个节点向后扫描查重时间复杂度为 $O(n^2)$在链表较短时可以接受但每次查询都是线性的面对长度为 20000 的链表时开销很大。「这个值是否已出现」本质上是一个查找问题。哈希表Hash Table可以将单次查询从线性时间降到期望常数时间因此是本题最自然、最优化的选择。算法分三步创建哈希表vis记录已经访问过被保留的节点值创建虚拟头节点pre令pre.next head。虚拟头节点的作用是统一处理「删除头节点」这类边界情况避免对头节点做特判遍历链表若pre.next.val已经存在于vis中说明当前节点是重复节点执行删除操作pre.next pre.next.next注意此时pre本身不移动以便继续检查下一个节点否则将pre.next.val加入vis并将pre前进到pre.next。遍历结束后返回head即完成去重。复杂度分析时间复杂度$O(n)$链表只被遍历一次每次哈希表查询/插入为期望 $O(1)$空间复杂度$O(n)$哈希表vis最多存放 $n$ 个不同的值。其中 $n$ 为链表的长度。多语言实现详解仓库中每道题都在题目目录下提供独立的可运行源码文件Solution.*与文档中的代码块一一对应。下面逐语言分析实现要点。Python3源码文件lcci/02.01.Remove Duplicate Node/Solution.pyclass Solution: def removeDuplicateNodes(self, head: ListNode) - ListNode: vis set() pre ListNode(0, head) while pre.next: if pre.next.val in vis: pre.next pre.next.next else: vis.add(pre.next.val) pre pre.next return head要点Python 的set底层基于哈希表ListNode(0, head)构造虚拟头节点时把head挂在其next上0仅作占位值。while pre.next在链表为空时直接不进入循环天然处理空链表边界。Java源码文件lcci/02.01.Remove Duplicate Node/Solution.javaclass Solution { public ListNode removeDuplicateNodes(ListNode head) { SetInteger vis new HashSet(); ListNode pre new ListNode(0, head); while (pre.next ! null) { if (vis.add(pre.next.val)) { pre pre.next; } else { pre.next pre.next.next; } } return head; } }要点这里巧妙利用了Set.add()的返回值——add成功值原本不存在返回true失败返回false。因此if (vis.add(...))同时完成了「查重 记录」两步代码更简洁。注意HashSet对Integer的判重基于equals与数值语义一致。C源码文件lcci/02.01.Remove Duplicate Node/Solution.cppclass Solution { public: ListNode* removeDuplicateNodes(ListNode* head) { unordered_setint vis; ListNode* pre new ListNode(0, head); while (pre-next) { if (vis.count(pre-next-val)) { pre-next pre-next-next; } else { vis.insert(pre-next-val); pre pre-next; } } return head; } };要点unordered_setint::count()返回 0 或 1可作存在性判断vis.insert()显式记录新值。注意pre是new出来的堆节点在真实工程中需注意内存释放面试手写时通常可忽略或改用栈上节点。Go源码文件lcci/02.01.Remove Duplicate Node/Solution.gofunc removeDuplicateNodes(head *ListNode) *ListNode { vis : map[int]bool{} pre : ListNode{0, head} for pre.Next ! nil { if vis[pre.Next.Val] { pre.Next pre.Next.Next } else { vis[pre.Next.Val] true pre pre.Next } } return head }要点Go 的map[int]bool即哈希表读取不存在的键返回零值false因此if vis[pre.Next.Val]可直接判断是否已出现。ListNode{0, head}以复合字面量构造虚拟头节点字段顺序对应结构体定义Val int; Next *ListNode。TypeScript源码文件lcci/02.01.Remove Duplicate Node/Solution.tsfunction removeDuplicateNodes(head: ListNode | null): ListNode | null { const vis: Setnumber new Set(); let pre: ListNode new ListNode(0, head); while (pre.next) { if (vis.has(pre.next.val)) { pre.next pre.next.next; } else { vis.add(pre.next.val); pre pre.next; } } return head; }要点TypeScript 的Setnumber在类型层面约束键为数值has/add分工明确逻辑与 Python 版本一致。注意pre声明为let因为其引用会随遍历不断推进。JavaScript源码文件lcci/02.01.Remove Duplicate Node/Solution.jsvar removeDuplicateNodes function (head) { const vis new Set(); let pre new ListNode(0, head); while (pre.next) { if (vis.has(pre.next.val)) { pre.next pre.next.next; } else { vis.add(pre.next.val); pre pre.next; } } return head; };要点与 TypeScript 版逻辑完全一致new ListNode(0, head)依赖题目给定的构造函数签名function ListNode(val)与next属性赋值。Rust源码文件lcci/02.01.Remove Duplicate Node/Solution.rsuse std::collections::HashSet; impl Solution { pub fn remove_duplicate_nodes(mut head: OptionBoxListNode) - OptionBoxListNode { let mut vis HashSet::new(); let mut pre ListNode::new(0); pre.next head; let mut cur mut pre; while let Some(node) cur.next.take() { if vis.contains(node.val) { cur.next node.next; } else { vis.insert(node.val); cur.next Some(node); cur cur.next.as_mut().unwrap(); } } pre.next } }要点Rust 的链表用OptionBoxListNode表示所有权语义要求借用mut pre遍历cur.next.take()取出当前节点的所有权用于判断contains命中时直接丢弃重复节点cur.next node.next未命中时把节点放回cur.next Some(node)并推进cur。这是 Rust 所有权模型下删除链表节点的标准写法。Swift源码文件lcci/02.01.Remove Duplicate Node/Solution.swiftclass Solution { func removeDuplicateNodes(_ head: ListNode?) - ListNode? { var vis SetInt() let pre ListNode(0, head) var current: ListNode? pre while current?.next ! nil { if vis.insert(current!.next!.val).inserted { current current?.next } else { current?.next current?.next?.next } } return head } }要点Swift 的Set.insert(_:)返回(inserted: Bool, memberAfterInsert: ...)元组取.inserted判断是否新插入pre用let声明其引用不变遍历指针current用var且为可选类型配合current?.next安全访问。进阶不使用临时缓冲区怎么解题目原文的 Follow Up 是如果不得使用临时缓冲区即空间复杂度 $O(1)$该如何解决从源码结构与官方解法看哈希表方案的空间代价是 $O(n)$。若不允许额外空间则退化为双重循环的暴力解法对链表中的每个节点用一个内层指针扫描其后的所有节点逐个删除值相同的后继节点每处理一个节点内层都需 $O(n)$ 时间总时间复杂度为 $O(n^2)$空间复杂度降为 $O(1)$满足「不使用临时缓冲区」的约束。该做法的时间代价较高适合链表较短或对空间有严格要求的场景。需要说明的是文档与仓库中未提供该进阶方案的实现代码此处仅基于题目约束给出推导结论不杜撰具体代码。一题一仓库如何在本仓库中查看与复现本仓库doocs/leetcode为每道题建立了独立目录统一存放题解文档与多语言源码本题的完整资料位于题解文档英文版 / 中文版源码文件Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.js、Solution.rs、Solution.swift均位于 lcci/02.01.Remove Duplicate Node/ 目录下仓库中同类链表题也遵循同样的「文档 多语言 Solution」组织模式例如 面试题 02.02 返回倒数第 k 个节点、面试题 02.04 分割链表。阅读这些目录时可以横向对比各语言在「虚拟头节点」「哨兵节点」等技巧上的写法差异加深对链表操作的理解。小结面试题 02.01 是一道经典的链表基础题核心考点有三虚拟头节点dummy node统一删除逻辑规避头节点特判哈希表查重将「是否出现」的判定从线性降到期望常数使整体达到 $O(n)$保留首次出现遍历方向从前向后首次遇到的值记入vis后续重复值一律删除天然满足题目要求。掌握「哈希表 虚拟头节点」的组合套路后可迁移至数组中重复元素移除、字符串去重等同类问题是面试高频基础能力之一。赞分享示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐AlgoNote 链表算法题精讲0083 删除排序链表中的重复元素LeetCode 单链表去重AlgoNote 链表算法题精讲0083 删除排序链表中的重复元素LeetCode 单链表去重 本文是《算法通关手册》 AlgoNote https://教程文档知识库LeetCode 83删除排序链表中的重复元素 Remove Duplicates from Sorted ListGo 题解LeetCode 83删除排序链表中的重复元素 Remove Duplicates from Sorted ListGo 题解 本文围绕 LeetCode示例工程LeetCode 203 移除链表元素Remove Linked List Elements题解虚拟节点 dummy 与链表面试 bug 防范指南LeetCode 203 移除链表元素Remove Linked List Elements题解虚拟节点 dummy 与链表面试 bug 防范指南 本文以文档教程知识库上一篇freeCodeCamp CSS Flexbox 教程实战用 flex-direction: column 让弹性子项垂直堆叠下一篇Step 0: Problem Formulation创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考