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

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

## 问题概述

在LeetCode的链表问题中，"删除排序链表中的重复元素"（Remove Duplicates from Sorted List）是一个经典的基础题目。题目要求我们给定一个已排序的链表，删除所有重复的元素，使得每个元素只出现一次。最终返回删除后的链表。

### 题目描述
- **题目编号**：83
- **难度**：简单
- **链接**：https://leetcode.com/problems/remove-duplicates-from-sorted-list/

**示例**：
```python
输入: 1->1->2
输出: 1->2

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

理解题目

首先，我们需要明确几个关键点： 1. 链表已排序：这意味着所有重复的元素都是相邻的，这大大简化了问题。 2. 删除重复元素：我们需要保留每个元素的一个实例，而不是全部删除。 3. 返回修改后的链表：我们需要在原链表上进行修改，而不是创建一个新的链表。

解题思路

方法一：直接遍历法

这是最直观的解法。我们可以遍历链表，比较当前节点和下一个节点的值。如果相同，就跳过下一个节点；如果不同，就继续遍历。

步骤： 1. 初始化一个指针 current 指向链表的头节点。 2. 遍历链表，直到 current 或 current.next 为 None： - 如果 current.val == current.next.val，则跳过 current.next，直接让 current.next 指向 current.next.next。 - 否则，移动 current 到 current.next。 3. 返回头节点。

代码实现（Python）：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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)，其中 n 是链表的长度。我们只需要遍历一次链表。 空间复杂度：O(1)，没有使用额外的空间。

方法二：递归法

虽然递归法在空间复杂度上不如直接遍历法高效，但它提供了一种更简洁的思考方式。

思路： 1. 如果链表为空或只有一个节点，直接返回链表。 2. 递归处理 head.next。 3. 如果 head.val == head.next.val，则跳过 head.next，直接返回 head。 4. 否则，返回 head。

代码实现（Python）：

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，应返回 None。 2. 单节点链表：输入为 1->None，应返回原链表。 3. 全重复链表：输入为 1->1->1->None，应返回 1->None。 4. 无重复链表：输入为 1->2->3->None，应返回原链表。

测试用例示例：

# 测试用例1：空链表
assert deleteDuplicates(None) is None

# 测试用例2：单节点链表
head = ListNode(1)
assert deleteDuplicates(head) == head

# 测试用例3：全重复链表
head = ListNode(1, ListNode(1, ListNode(1)))
result = deleteDuplicates(head)
assert result.val == 1 and result.next is None

# 测试用例4：无重复链表
head = ListNode(1, ListNode(2, ListNode(3)))
result = deleteDuplicates(head)
assert result.val == 1 and result.next.val == 2 and result.next.next.val == 3

常见错误与陷阱

在解决这个问题时，初学者可能会遇到以下错误： 1. 未处理空链表：直接访问 head.val 或 head.next 会导致 AttributeError。 2. 指针移动逻辑错误：在发现重复时，忘记移动指针或错误地移动指针。 3. 修改链表后未返回头节点：在修改链表后，需要返回链表的头节点。

错误示例：

def deleteDuplicates(head: ListNode) -> ListNode:
    current = head
    while current.next:  # 错误：未检查 current 是否为 None
        if current.val == current.next.val:
            current.next = current.next.next
        current = current.next  # 错误：在跳过节点后未检查 current.next
    return head

扩展问题

问题变种：删除所有重复元素

LeetCode中还有一个类似的问题（第82题），要求删除所有重复的元素，包括唯一的元素。例如：

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

解法思路： 1. 使用一个哑节点（dummy node）作为链表的起始节点，简化头节点的处理。 2. 使用两个指针 prev 和 current，prev 指向当前不重复的节点，current 用于遍历链表。 3. 当发现重复时，跳过所有重复节点。

代码实现（Python）：

def deleteAllDuplicates(head: ListNode) -> ListNode:
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy
    current = head
    while current:
        while current.next and current.val == current.next.val:
            current = current.next
        if prev.next == current:
            prev = prev.next
        else:
            prev.next = current.next
        current = current.next
    return dummy.next

总结

删除排序链表中的重复元素是一个基础的链表操作问题，通过直接遍历法可以高效解决。关键点在于： 1. 利用链表已排序的特性，只需比较相邻节点。 2. 注意指针的移动逻辑，避免空指针异常。 3. 考虑边界条件，如空链表或全重复链表。

掌握这个问题不仅有助于理解链表的基本操作，还能为更复杂的链表问题打下基础。建议读者在理解后尝试解决其变种问题，如删除所有重复元素的版本，以加深对链表操作的理解。

参考资料

1. LeetCode官方题解：https://leetcode.com/problems/remove-duplicates-from-sorted-list/solution/
2. 《算法导论》中的链表章节。
3. Python官方文档关于链表的实现。

”`