1. 概述
链表去重是常见的数据结构问题之一。该问题有多种变体，本文将围绕其通用解法展开讨论。
我们将依次介绍以下内容：
- 原始的暴力解法
- 使用集合优化后的高效解法
- 针对小整数场景的优化方法
- 针对有序链表的线性解法
- 各种方法的性能对比与适用场景
所有方法都保持原链表中元素的出现顺序，仅保留每个元素的第一次出现。
2. 问题定义
给定一个链表 A，包含 n 个节点，我们的目标是返回一个新的链表，其中不含重复元素。
换句话说，新链表中每个元素最多只出现一次。例如：
输入：1 → 2 → 3 → 2 → 4
输出：1 → 2 → 3 → 4
3. 暴力解法（Brute Force）
✅ 思路
使用两个嵌套循环：
- 外层遍历原链表中的每个元素
- 内层遍历结果链表，检查当前元素是否已存在
若不存在，则添加到结果链表中。
💡 示例代码（Java 伪代码）
algorithm removeDuplicatesNaive(A):
answer <- new LinkedList()
iIter <- A.head
while iIter != null:
jIter <- answer.head
isAdded <- false
while jIter != null:
if iIter.value == jIter.value:
isAdded <- true
break
jIter <- jIter.next
if not isAdded:
answer.add(iIter.value)
iIter <- iIter.next
return answer
⚠️ 复杂度分析
- 时间复杂度：**O(n²)**（最坏情况）
- 空间复杂度：**O(n)**（结果链表）
虽然实现简单，但效率较低，尤其在数据量大时表现较差。
4. 使用集合的优化解法（Faster Approach）
✅ 思路
使用一个集合（Set）来记录已出现的元素：
- 每次遍历一个节点时，检查集合中是否存在该值
- 若不存在，将其添加到结果链表和集合中
💡 示例代码（Java 伪代码）
algorithm removeDuplicatesFaster(A):
answer <- new LinkedList()
seen <- new TreeSet()
iter <- A.head
while iter != null:
if not seen.contains(iter.value):
answer.add(iter.value)
seen.add(iter.value)
iter <- iter.next
return answer
⚠️ 复杂度分析
- 时间复杂度：**O(n log n)**（基于 TreeSet 的插入和查找）
- 空间复杂度：O(n)
使用 TreeSet 可以实现 log n 时间内的查找和插入，适用于一般场景。
✅ 提示：如果对顺序无要求，可以使用
HashSet替代TreeSet，平均查找时间为 O(1)，效率更高。
5. 小整数优化解法（Small Integer Values）
✅ 思路
当链表中元素是范围较小的整数时，可以使用布尔数组代替集合。
例如，元素范围为 [0, MaxVal]，则创建一个大小为 MaxVal + 1 的布尔数组，用于标记某个值是否已被添加。
💡 示例代码（Java 伪代码）
algorithm removeDuplicatesSmallIntegers(A):
answer <- new LinkedList()
isAdded <- new boolean[MaxVal + 1] // 初始化为 false
iter <- A.head
while iter != null:
val <- iter.value
if not isAdded[val]:
answer.add(val)
isAdded[val] <- true
iter <- iter.next
return answer
⚠️ 复杂度分析
- 时间复杂度：O(n + MaxVal)
- 空间复杂度：O(MaxVal)
适用于元素范围较小的情况，如处理 0~1000 之间的整数。
⚠️ 注意：如果存在负数，可以通过偏移转换为非负数处理。
6. 有序链表优化解法（Sorted Linked List）
✅ 思路
当链表本身是有序的时，重复元素一定是相邻的。因此我们只需比较当前元素与结果链表的最后一个元素即可。
💡 示例代码（Java 伪代码）
algorithm removeDuplicatesSorted(A):
answer <- new LinkedList()
iter <- A.head
while iter != null:
if answer.isEmpty() or answer.getLast() != iter.value:
answer.add(iter.value)
iter <- iter.next
return answer
⚠️ 复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)
这是目前最高效的通用解法之一，适用于已排序链表。
7. 各种方法对比总结
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力解法 | O(n²) | O(n) | 通用，但效率低 |
| 集合优化 | O(n log n) | O(n) | 通用，推荐一般情况使用 |
| 小整数优化 | O(n + MaxVal) | O(MaxVal) | 元素为小整数时效率高 |
| 有序链表优化 | O(n) | O(n) | 链表已排序时最优 |
8. 总结
链表去重问题有多种解法，选择时应根据具体场景进行权衡：
- 若链表无序且元素类型非整数，推荐使用集合优化解法
- 若链表中是小整数，使用布尔数组优化空间和时间
- 若链表有序，直接比较相邻元素即可实现线性复杂度
- 暴力解法适合理解原理，但不推荐用于实际场景
掌握这些方法有助于在不同场景下快速选择最优解法，提升代码性能与可维护性。