0083. Remove Duplicates from Sorted List

题目信息

题号:
  1. 删除排序链表中的重复元素

难度:

Easy

主题:

单链表、有序去重、连续重复段

原题:

LeetCode 0083

重点:

从记录已见值,推导到利用有序性原地压缩每个连续值段

题目重述

给定一个按非递减顺序排列的单链表 head,删除其中的重复节点,使每个不同值只保留一个节点, 并返回去重后的链表。

保留下来的节点必须维持原有相对顺序。与 0082 不同,本题不会删除整个重复值段,而是保留该值段的第一个节点。

链表节点数在 0..300 范围内,节点值在 -100..100 范围内。

自建示例

输入:0 -> 0 -> 0 -> 2 -> 2 -> 5
输出:0 -> 2 -> 5

三个 0 保留第一个,两个 2 保留第一个,5 原样保留。

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

每个连续值段都压缩为一个原节点。

输入:空链表
输出:空链表

没有节点时直接返回空指针。

C++ 实现

#include <unordered_set>

class Solution {
private:
    ListNode* setBased(ListNode* head) {
        std::unordered_set<int> seen;
        ListNode dummy(0);
        ListNode* tail = &dummy;

        for (ListNode* node = head; node != nullptr; ) {
            ListNode* next = node->next;

            if (seen.insert(node->val).second) {
                tail->next = node;
                tail = node;
                tail->next = nullptr;
            }

            node = next;
        }

        return dummy.next;
    }

    ListNode* recursiveCompress(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }

        head->next = recursiveCompress(head->next);

        while (head->next != nullptr && head->next->val == head->val) {
            head->next = head->next->next;
        }

        return head;
    }

    ListNode* adjacentScan(ListNode* head) {
        ListNode* current = head;

        while (current != nullptr) {
            while (current->next != nullptr && current->next->val == current->val) {
                current->next = current->next->next;
            }

            current = current->next;
        }

        return head;
    }

public:
    ListNode* deleteDuplicates(ListNode* head) {
        return adjacentScan(head);
    }
};

题解

通用去重

不利用有序性时,可以用集合记录已经出现的值。第一次读到某个值时把该节点接到结果尾部,后续相同值全部跳过。 这种方法适用于无序链表,但需要 O(n) 额外空间,也忽略了本题最关键的有序结构。

连续值段

链表按非递减顺序排列,所以相同值必然连续出现。链表可以分成若干值段:

0 -> 0 -> 0 | 2 -> 2 | 5

每段只需保留第一个节点,并让它直接连接到下一段的第一个节点。进入更大的值后,当前值不会再次出现, 因此不需要集合或全局计数。

递归压缩

递归方法先去重 head->next 开始的后缀,再检查处理后的后继是否与 head 同值。若同值,就持续绕过这些节点。

后缀已经保证每个值至多保留一次,所以递归返回后通常只需一次比较;代码保留 while,使局部逻辑独立且更容易验证。 递归层数最多为节点数,因此需要 O(n) 调用栈。

单指针状态

迭代方法让 current 始终指向当前值段保留的第一个节点。每轮外层循环开始时:

  • 从链表头到 current 的部分已经去重;

  • current 本身必须保留;

  • current->next 开始仍可能包含同值节点。

只要后继与 current 同值,就执行:

current->next = current->next->next;

这会绕过一个重复节点,同时保持 current 不动,以便继续检查新的后继。

连续绕过

输入 1 -> 1 -> 1 -> 2 时,删除第一个重复后,current->next 仍然是 1。若只使用一次 if, 第三个 1 会被错误保留。因此必须使用内层 while,直到后继为空或值发生变化。

current

后继

动作

第一个 1

第二个 1

绕过第二个 1

第一个 1

第三个 1

继续绕过

第一个 1

2

当前值段完成

2

空

保留尾节点并结束

不同值保留

删除条件只在 current->next->val == current->val 时成立。遇到第一个更大的值后,内层循环立即停止, 该节点仍连接在链表中,并在下一轮成为新值段的代表。

每个值段的第一个节点从不被绕过,其余同值节点全部被绕过。因此最终每个不同值恰好保留一次, 且保留的是输入中最先出现的原节点。

头节点稳定

本题无论头部值重复多少次,都保留第一个头节点,结果头不会改变,所以不需要哨兵节点。 0082 会删除整个重复值段,头部可能整体消失,才需要哨兵节点保存可修改的前驱位置。

节点处理

主方法只修改 next 指针,不交换节点值,也不创建结果节点。被绕过节点的释放策略由调用环境负责; LeetCode 的函数只需返回重新连接后的链表头。

复杂度

集合方法时间 O(n)、额外空间 O(n)。递归方法时间 O(n),调用栈 O(n)。 单指针方法中每个节点最多被检查和绕过一次,时间 O(n),额外空间 O(1)。