LeetCode 面试题 02.01. 移除重复节点

约 8 分钟
文章信息 9 个分类 4 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 字节跳动 美团 滴滴 程序员面试金典（第 6 版）
标签
哈希表 双指针 链表 元素去重问题
目录

题目描述

✅ 面试题 02.01. 移除重复节点

image-20230305203836056

题意分析

给一个单链表，把值重复出现的节点删掉，同一个值只保留第一次出现的那个节点，其余全部移除，最后返回处理后的链表头。

最关键的一条隐含约束是：链表没有排序。这和 83、82 那两道「删除排序链表中的重复元素」有本质区别——那里重复值必然相邻，这里 [1,2,3,3,2,1] 中的两个 1 相隔了四个节点，只比较相邻节点根本发现不了。

「保留第一次出现」还规定了保留哪一个，所以剩下节点的相对顺序必须和原链表一致，不能先排序再去重。

数据规模是链表长度不超过 2 万、节点值在 0 到 2 万之间，这个值域信息在优化时用得上。

题目末尾的进阶问「如果不得使用临时缓冲区该怎么解决」，等于把「用额外空间换时间」和「不用额外空间但接受更高时间代价」两条路都摆到台面上了，面试时两种都要能说。

边界上要覆盖：空链表、只有一个节点、以及首节点就参与重复（比如 [1,1,1]，结果只剩一个节点）。

解法：哈希集合记录已保留节点

核心思路

不用额外空间的做法是双层循环：外层固定一个已保留节点，内层从它往后扫，把所有与它同值的节点摘掉。逻辑直白，但每个保留节点都要扫一遍后缀，最坏是 $O(n^2)$，两万个节点时约四亿次比较。

瓶颈在于「判断当前值以前是否出现过」这件事被反复地用线性扫描来完成。而这正是哈希集合最擅长的：把已保留过的值全部记下来，之后每次询问只要常数时间。

于是整趟遍历维持这样一个不变量：处理到节点 cur 之前，集合 seen 里装的恰好是「已经被确认保留、且位于 cur 之前」的所有节点值，而 pre 恰好指向这些保留节点中的最后一个。

有了这个不变量，每个节点的判定就只剩两种走向——值在 seen 里，说明它是重复的，让 pre 直接跨过它；值不在 seen 里，说明它是首次出现，加入集合并把 pre 推进到它身上。

需要格外留心的是 pre 的推进时机：删除节点时 pre 不能动，因为「最后一个保留节点」还是原来那个；只有真正保留了当前节点，pre 才向后走一步。把这条写进不变量里，就不会出现「删完一个节点后 pre 指向了已被摘掉的节点」这种断链事故。

头节点本身也可能被删（比如 [1,1] 中如果规则是保留后者），为了让头节点和其它节点走同一条代码路径，前面挂一个哑节点，最后返回 dummy.next。

解题步骤

  • 建一个哈希集合 seen 和一个哑节点 dummy，令 dummy.next = head。哑节点的作用是给头节点也配一个前驱，这样删除逻辑不需要为「删的是不是头」单独写分支。
  • 令 pre = dummy、cur = head。pre 的语义固定为「最后一个已确认保留的节点」，cur 的语义固定为「当前正在判定的节点」，两个变量的含义在整个循环里都不许改变。
  • 循环条件是 cur != null。空链表时 cur 一开始就是 null，循环体一次都不进，最后返回 dummy.next 即 null，边界天然被覆盖。
  • 若 seen 已包含 cur.val，执行 pre.next = cur.next，把 cur 从链上摘掉。这里不能动 pre——被摘掉的节点不能成为任何节点的前驱，pre 必须继续指向上一个保留下来的节点。
  • 否则把 cur.val 加入 seen，并令 pre = cur。此时 cur 被确认保留，它成为新的「最后一个保留节点」，不变量顺利推进。
  • 两个分支结束后统一执行 cur = cur.next。注意这一步放在分支外面是安全的：删除分支里改的是 pre.next，cur.next 本身没有被修改，所以仍然指向正确的下一个节点。
  • 遍历结束后返回 dummy.next。之所以不能直接返回 head，是因为若原来的头节点在某些变体规则下被删，head 就成了野指针；用哑节点取值是更稳的写法。

以 head = [1,2,3,3,2,1] 走一遍：初始 seen 为空，pre = dummy，cur 指向第一个 1。第一步，1 不在 seen 中，加入后 seen = {1}，pre 移到节点 1。第二步 cur 到 2，不在集合中，seen = {1,2}，pre 移到节点 2。第三步 cur 到第一个 3，不在集合中，seen = {1,2,3}，pre 移到该节点。第四步 cur 到第二个 3，命中集合，执行 pre.next = cur.next，于是第一个 3 直接指向后面的 2，pre 保持不动。第五步 cur 到那个 2，命中集合，pre.next 被改成它后面的 1，pre 仍不动。第六步 cur 到最后的 1，命中集合，pre.next 被改成 null。cur 变成 null，循环结束。此时链表是 1 → 2 → 3，返回 dummy.next 即节点 1。可以注意到 pre 从第三步之后就再没移动过，这正是「连续删除多个节点」时不变量仍然成立的体现。

代码实现

class Solution {
    // 遍历时用哈希集合记录已经保留过的值，当前值已出现就让前驱节点直接跳过当前节点。
    public ListNode removeDuplicateNodes(ListNode head) {
        Set<Integer> seen = new HashSet<>();
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode pre = dummy;
        ListNode cur = head;

        while (cur != null) {
            if (seen.contains(cur.val)) {
                pre.next = cur.next;
            } else {
                seen.add(cur.val);
                pre = cur;
            }
            cur = cur.next;
        }

        return dummy.next;
    }
}

func removeDuplicateNodes(head *ListNode) *ListNode {
    // 遍历时用哈希集合记录已经保留过的值，当前值已出现就让前驱节点直接跳过当前节点。
    seen := make(map[int]struct{})
    dummy := &ListNode{Next: head}
    pre := dummy
    cur := head

    for cur != nil {
        if _, exists := seen[cur.Val]; exists {
            pre.Next = cur.Next
        } else {
            seen[cur.Val] = struct{}{}
            pre = cur
        }
        cur = cur.Next
    }

    return dummy.Next
}

复杂度分析

  • 时间复杂度：$O(n)$，链表只走一趟，每个节点做一次集合查询和至多一次指针改写，均摊都是常数。
  • 空间复杂度：$O(n)$，哈希集合最坏要装下全部 n 个互不相同的值；若按进阶要求禁用缓冲区，可用双层循环把空间压到 $O(1)$，代价是时间升到 $O(n^2)$。

关键点总结

  • 判断「以前是否出现过」是哈希集合的标准场景，它把双层循环里那次线性查找压成常数，是从 $O(n^2)$ 降到 $O(n)$ 的唯一改动点。
  • 链表删除类题目一律先问自己「头节点会不会被删」，会就挂哑节点；这样删除逻辑只有一条路径，白板上少写一半分支。
  • pre 与 cur 的语义必须在整个循环里保持恒定：pre 是最后一个保留节点，cur 是待判定节点。删除时 pre 不动、保留时 pre 前进，这条规则比记代码形状更可靠。
  • cur = cur.next 能安全地放在分支外，前提是删除操作只改了 pre.next 而没有碰 cur.next；一旦写法里动了 cur.next，就必须先把后继存下来。
  • 面试视角：本题几乎一定会被追问进阶「不使用临时缓冲区」，要能立刻给出双层循环版本并说清 $O(n^2)$ 时间、$O(1)$ 空间的取舍；节点值域只有 0 到 2 万，还可以补一句「用 bitset 或布尔数组能把常数和空间都压得更低」。

易错点总结

  • 错误写法：套用 83 题的相邻比较写法 if (cur.val == cur.next.val) → head = [1,2,3,3,2,1] 只能删掉相邻的那对 3，返回 [1,2,3,2,1]，因为本题链表没有排序。
  • 错误写法：删除节点时也执行 pre = cur → head = [1,1,1] 中删掉第二个 1 后 pre 指向了已被摘掉的节点，第三个 1 的删除会改到一条脱离主链的 next 上，结果变成 [1,1]。
  • 错误写法：不用哑节点，直接从 pre = head、cur = head.next 开始，且不特判空链表 → head 为 null 时访问 head.next 立刻空指针。
  • 错误写法：先执行 cur = cur.next 再做删除判断 → 判定和摘除作用在不同节点上，链表结构直接错乱。
  • 错误写法：删除时写成 cur = cur.next; pre.next = cur; 但把两句顺序写反 → 先改 pre.next 再取 cur.next 时读到的已经是新链，会跳过或重复处理节点；这类题一律先取后继再改指针最稳。
  • 错误写法：把已访问过的所有节点值加入集合，而不是只加保留下来的 → 结果虽然相同，但如果题目变体改成「重复的全部删掉、一个不留」，这两种记法就会给出不同答案，含义必须先定死。
  • 错误写法：用 List.contains 代替 HashSet.contains → 每次查询退化成线性扫描，两万个节点时整体又变回 $O(n^2)$，等于白用了额外空间。
  • 错误写法：写进阶版双层循环时，内层删掉一个节点后仍然把扫描指针往后挪 → head = [1,1,1] 中摘掉第二个 1 后指针直接跳到第三个 1 之后，返回 [1,1]；删除之后指针必须原地不动，只有未删除时才前进。
  • 错误写法：最后返回 head 而不是 dummy.next → 本题保留首次出现的节点，head 恰好不会被删，所以能侥幸通过；但换成「保留最后一次出现」的变体立刻出错，习惯性返回 dummy.next 更安全。

相似题目

题目 难度 考察点
82. 删除排序链表中的重复元素 II 中等 已排序，重复值一个不留，需连续跳过整段
83. 删除排序链表中的重复元素 简单 已排序，只比相邻节点即可，不需要额外空间
203. 移除链表元素 简单 按给定值删除，哑节点的最小练习
237. 删除链表中的节点 中等 拿不到前驱，只能靠复制后继值来「假删」
剑指 Offer 18. 删除链表的节点 简单 只删第一个匹配节点，要处理删头的情况
面试题 02.03. 删除中间节点 简单 与 237 同套路，考察对单链表限制的理解