Leetcode 83. Remove Duplicates from Sorted List

问题描述

给定一个排序链表，请删除所有重复的元素，使得每个元素只出现一次。

示例 1：

输入:

Copy Code
1 -> 1 -> 2

输出:

Copy Code
1 -> 2

示例 2：

输入:

Copy Code
1 -> 1 -> 2 -> 3 -> 3

输出:

Copy Code
1 -> 2 -> 3

提示

链表中每个节点的值都已经按升序排列。
链表中的节点个数在 [0, 300] 范围内。
链表中的每个节点值在 [-100, 100] 范围内。

题目分析

核心思想

该问题要求我们删除已排序链表中的重复元素。由于链表已经是排序的，我们可以利用链表的顺序特性，直接遍历链表并在遍历过程中删除重复元素。这种方式非常高效，并且能够保证算法在时间和空间上的最优表现。

具体来说，算法的核心思想是：

遍历链表，每次检查当前节点的值是否与下一个节点的值相同。
如果相同，则跳过下一个节点，即将当前节点的 next 指针指向下下一个节点。
如果不同，则继续遍历下一个节点。

这种方式的时间复杂度为 O(n)，其中 n 为链表的节点数量，因为每个节点只会被访问一次。空间复杂度为 O(1)，因为我们只使用了常数空间。

解题步骤

定义链表节点
链表的节点定义通常会包含一个值和指向下一个节点的指针。在本题中，节点的定义通常为：

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

算法流程
- 创建一个指针 current，初始指向链表的头节点。
- 遍历链表，检查每个节点是否与下一个节点重复。
- 如果重复，则跳过下一个节点。
- 如果不重复，则移动指针 current 到下一个节点。
- 直到遍历完整个链表。
边界情况
- 空链表：如果输入链表为空，直接返回空链表。
- 链表中所有节点都相同：这种情况下，算法应该最终返回仅包含一个节点的链表。
- 链表中没有重复元素：这种情况下，链表保持不变。
代码实现

pythonCopy Code
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

解释

我们定义了一个 ListNode 类，用来表示链表节点。
deleteDuplicates 函数的核心就是遍历链表，对于每一个节点，如果当前节点的值与下一个节点的值相同，则跳过下一个节点，否则继续向后移动。
函数返回的是修改后的链表头。

复杂度分析

时间复杂度：O(n)，其中 n 为链表的节点数。我们只需要遍历链表一次，检查每个节点与下一个节点的值。
空间复杂度：O(1)。我们只使用了常数级别的额外空间，除了输入链表和常量空间外，没有额外的空间开销。

示例与测试

示例 1

输入:

Copy Code
1 -> 1 -> 2

步骤:

首先，指针 current 指向链表的第一个节点，值为 1。
current 的下一个节点值也是 1，两个值相同，因此跳过下一个节点。
current 继续指向第二个节点（值为 2），此时没有更多的重复元素。
返回修改后的链表：1 -> 2

输出:

Copy Code
1 -> 2

示例 2

输入:

Copy Code
1 -> 1 -> 2 -> 3 -> 3

步骤:

指针 current 最初指向链表的第一个节点，值为 1。
current 的下一个节点值也是 1，两个值相同，因此跳过下一个节点。
current 移动到第二个节点（值为 2），没有重复元素。
current 移动到第三个节点（值为 3），current 的下一个节点值也是 3，因此跳过下一个节点。
返回修改后的链表：1 -> 2 -> 3

输出:

Copy Code
1 -> 2 -> 3

边界情况

空链表

输入:

Copy Code
None

输出:

Copy Code
None

链表所有节点相同

输入:

Copy Code
1 -> 1 -> 1 -> 1

步骤:

current 指向第一个节点，值为 1。
后续节点的值与当前节点相同，因此每次都会跳过。
返回修改后的链表：1

输出:

Copy Code
1

无重复元素的链表

输入:

Copy Code
1 -> 2 -> 3 -> 4

输出:

Copy Code
1 -> 2 -> 3 -> 4

场景应用

这个问题在实际开发中具有广泛的应用，尤其是在处理链表、队列等数据结构时，删除重复数据是常见的需求。例如，假设有一个排序的日志数据，记录了系统中出现的错误类型或访问次数，我们希望对这些日志数据进行去重处理以便分析。通过这种方法，我们可以高效地删除重复数据，提升后续处理的效率。

总结

在处理链表相关问题时，尤其是排序链表时，删除重复元素是一种典型的操作。通过遍历链表并检查每个节点与下一个节点的值，我们可以有效地去除重复项。这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)，非常高效，适用于大多数链表处理场景。