LeetCode 面试题 02.01. 移除重复节点
题目描述
题意分析
删除未排序链表中数值重复的节点，每种值只保留最早出现的那个节点，保留下来的节点仍按原来的相对顺序连接。重复值可能隔得很远，因此不能只比较相邻节点，也不能先排序再去重。
要返回去重后的头节点，空链表仍返回空。题面还要求考虑不使用临时缓冲区的情况，下面分别给出哈希记录与仅用指针扫描的处理。
解法：哈希集合记录已保留节点
核心思路
[!blue]
从头到尾扫描，用
seen保存前面已经保留的所有数值。当前值不在集合里，说明这是它第一次出现，应保留该节点并加入集合；若值已存在，则当前节点属于后续重复项，需要删除。单链表删除节点要修改它前一个保留节点的
next，所以同时维护当前节点cur和结果尾部pre。重复时执行pre.next = cur.next，让结果跳过当前节点；pre仍停在原处，因为被删除的节点不能充当下一轮结果中的前驱。保留新值时，当前节点成为新的结果尾部，才让
pre = cur。两种分支之后cur都向原后继推进，保证每个输入节点只检查一次；连续重复值也始终由同一个保留前驱逐个跳过。集合只在第一次出现时新增，所以最终每种值恰好保留第一次出现的节点。扫描顺序和剩余连接的先后都没有改变，满足稳定顺序；哑节点只统一前驱处理，不进入返回结果。
解题步骤
- 初始化空集合，将哑节点连到原头节点，
pre指向哑节点，cur指向原头。- 当前值已出现时，让
pre.next跳过cur，前驱保持不动。- 当前值未出现时加入集合，并将
pre移到当前保留节点。- 每轮都将
cur后移，扫描结束返回dummy.next。
代码实现
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(u)$，u 为不同值的数量。
关键点总结
[!green]
- 遇到重复节点时前驱仍是上一个保留节点。
- 原链表节点直接复用，顺序不变。
进阶：不使用缓冲区的双重扫描
核心思路
[!blue]
不用集合时，就让每个保留节点亲自清理它后面所有同值节点。外层指针
current从头向后移动，内层指针runner从它开始，检查runner.next是否与current同值。同值就跳过
runner.next，并保持runner不动，继续检查刚接上来的后继；不同值才让runner后移。这样一轮内层扫描结束，current后面已没有同值节点，而current作为这一数值的首次出现被保留。外层已经处理过的值在后缀中都已清除，因此下一次走到的
current必然是另一个值的首次出现。重复清理直到末尾，每种值只剩首个节点，原相对顺序也不会改变。代价是反复扫描后缀，用平方时间换取常数额外空间。
解题步骤
- 令
current从链表头逐个走过保留节点。- 每轮让
runner = current，只要runner.next非空就继续检查。- 后继与当前值相同则断开该后继；否则移动
runner。- 当前值的后续重复项清理完后再移动外层指针，最后返回原头节点。
代码实现
class Solution {
public ListNode removeDuplicateNodes(ListNode head) {
for (ListNode current = head; current != null; current = current.next) {
ListNode runner = current;
while (runner.next != null) {
if (runner.next.val == current.val) {
runner.next = runner.next.next;
} else {
runner = runner.next;
}
}
}
return head;
}
}
func removeDuplicateNodes(head *ListNode) *ListNode {
for current := head; current != nil; current = current.Next {
runner := current
for runner.Next != nil {
if runner.Next.Val == current.Val {
runner.Next = runner.Next.Next
} else {
runner = runner.Next
}
}
}
return head
}
复杂度分析
- 时间复杂度：最坏 $O(n^2)$，所有值不同会依次扫描长度递减的后缀。
- 空间复杂度：$O(1)$，只有两个指针，不保存集合或新链表。
关键点总结
[!green]
- 外层节点负责保留首次出现，内层只删除它之后的同值节点。
- 检查后继而非当前扫描节点，才能直接通过前驱修改单链表连接。
- 删除后不移动内层前驱，保留后继时才推进。
易错点总结
[!yellow]
- 删除后不能把前驱移到被删节点，否则下一次修改的是已经脱离结果的连接。
- 链表无序，只检查相邻值无法删除远处重复项；排序又会改变首次出现顺序。
- 无缓冲区解法删除
runner.next后要停留在原前驱，继续检查新接上来的后继，避免漏掉连续重复项。- 两种方法都直接复用原节点，只修改连接，不应把哑节点本身当成答案返回。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 83. 删除排序链表中的重复元素 | 简单 | 原题链表已排序，重复值相邻，本题无序，需要记录此前见过的值。 |
| 217. 存在重复元素 | 简单 | 集合可判断重复是否出现，本题在发现重复时还要正确跳过节点并保留首次出现者。 |