设计算法删除单链表中的重复元素（数据结构）

### 设计算法删除单链表中的重复元素 对于无序单链表，可以通过遍历整个列表并使用额外的数据结构（如哈希表或集合）记录已经遇到过的值来实现去重操作。这样可以在一次遍历过程中完成所有重复项的移除工作[^1]。 #### 方法一： 使用辅助空间 (Hash Table) 此方法适用于不知道输入范围的情况。创建一个新的空集合用于存储已访问节点的值；接着从头到尾扫描原链表，在每一步检查当前结点所指向的数据是否存在于该集合内： - 如果存在，则说明这是一个重复条目，此时应调整前驱指针绕过这个冗余单元； - 若不存在于集合之中则将其加入其中，并继续前进至下一个位置直到结束为止。 ```python class ListNode: def __init__(self, value=0, next=None): self.value = value self.next = next def remove_duplicates(head: ListNode) -> None: seen_values = set() current_node = head previous_node = None while current_node is not None: if current_node.value in seen_values: # Remove the node by skipping it. previous_node.next = current_node.next else: seen_values.add(current_node.value) previous_node = current_node current_node = current_node.next ``` 这种方法的时间复杂度为 O(n)，因为只需要遍历一遍链表即可完成任务。而由于采用了额外的空间保存见过的数值，所以其空间消耗也是线性的 O(n)。 #### 方法二： 不适用任何附加数据结构 如果不允许使用额外内存来进行优化处理的话，还可以考虑采用两层嵌套循环的方式解决这个问题。外层迭代器负责选取待比较的目标对象，而内部逻辑则是沿着后续路径逐个检验是否存在与其相匹配者——一旦发现即刻执行相应的剔除动作。不过需要注意的是这种方案虽然节省了临时变量开销但却带来了平方级别的运行时间成本O(n²)。 ```python def remove_duplicates_no_extra_space(head: ListNode) -> None: outer_current = head while outer_current and outer_current.next: inner_runner = outer_current while inner_runner.next: if inner_runner.next.value == outer_current.value: inner_runner.next = inner_runner.next.next else: inner_runner = inner_runner.next outer_current = outer_current.next ```