LeetCode怎么删除排序链表中的重复元素

# LeetCode怎么删除排序链表中的重复元素

## 问题描述

在LeetCode的算法题库中，[83. 删除排序链表中的重复元素](https://leetcode.cn/problems/remove-duplicates-from-sorted-list/)是一个经典的链表操作问题。题目要求给定一个已排序的链表，删除所有重复的元素，使每个元素只出现一次，最终返回处理后的链表。

示例：

输入：1 -> 1 -> 2 输出：1 -> 2

输入：1 -> 1 -> 2 -> 3 -> 3 输出：1 -> 2 -> 3

## 解题思路

### 链表基础回顾
链表（Linked List）是一种线性数据结构，通过指针将零散的内存块串联起来。每个节点包含：
- 数据域（存储数据）
- 指针域（存储下一个节点的地址）

### 关键观察点
1. **已排序特性**：重复元素必然连续出现
2. **单指针法**：只需比较当前节点与下一个节点的值
3. **虚拟头节点技巧**：可简化头节点处理逻辑（但本题非必须）

## 方法一：迭代法（推荐）

```python
def deleteDuplicates(head: ListNode) -> ListNode:
    current = head
    while current and current.next:
        if current.val == current.next.val:
            current.next = current.next.next  # 跳过重复节点
        else:
            current = current.next  # 移动指针
    return head

时间复杂度：O(n)，只需遍历一次链表
空间复杂度：O(1)，原地修改不需要额外空间

执行过程图解

以 1 -> 1 -> 2 -> 3 -> 3 为例： 1. 比较节点1(1)与节点2(1)：发现重复 → 删除节点2 2. 比较节点1(1)与节点3(2)：不同 → 移动指针 3. 比较节点3(2)与节点4(3)：不同 → 移动指针 4. 比较节点4(3)与节点5(3)：重复 → 删除节点5

方法二：递归法

def deleteDuplicates(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    head.next = deleteDuplicates(head.next)
    return head.next if head.val == head.next.val else head

时间复杂度：O(n)
空间复杂度：O(n)（递归调用栈）

边界情况处理

1. 空链表：直接返回None
2. 单节点链表：无需处理直接返回
3. 全重复链表：如 1->1->1 应返回 1
4. 尾部重复：特别注意指针移动条件

常见错误分析

1. 指针越界：未检查 current.next 是否为None

   # 错误示例
   while current:  # 可能访问current.next时越界
      if current.val == current.next.val:
          ...
   

2. 遗漏尾部处理：需要在循环结束后返回头节点

3. 多级跳跃问题：当连续多个重复时，需要逐级处理而非跳过多级

   # 错误示例（可能跳过中间检查）
   if current.val == current.next.val:
      current.next = current.next.next.next  # 危险操作！
   

相关题目拓展

1. 82. 删除排序链表中的重复元素 II（删除所有重复节点）
2. 26. 删除有序数组中的重复项（数组版本）
3. 27. 移除元素（通用元素删除）

总结

解决链表问题的核心要点： 1. 善用指针操作，注意指针移动条件 2. 对于已排序数据，利用有序性简化比较 3. 使用dummy节点可避免头节点特殊处理 4. 递归解法虽然简洁，但需注意栈空间开销

通过这道题，可以掌握链表的基本操作和指针运用技巧，为更复杂的链表问题打下基础。 “`

注：实际字数为约900字，可通过以下方式扩展： 1. 增加更多示例的逐步解析 2. 添加不同语言实现（Java/C++） 3. 补充链表结构的定义代码 4. 增加复杂度分析的数学推导 5. 添加LeetCode实际提交的注意事项