0083. Remove Duplicates from Sorted List ======================================== 题目信息 -------- :题号: 0083. 删除排序链表中的重复元素 :难度: Easy :主题: 单链表、有序去重、连续重复段 :原题: `LeetCode 0083 `_ :重点: 从记录已见值,推导到利用有序性原地压缩每个连续值段 题目重述 -------- 给定一个按非递减顺序排列的单链表 ``head``,删除其中的重复节点,使每个不同值只保留一个节点, 并返回去重后的链表。 保留下来的节点必须维持原有相对顺序。与 0082 不同,本题不会删除整个重复值段,而是保留该值段的第一个节点。 链表节点数在 ``0..300`` 范围内,节点值在 ``-100..100`` 范围内。 自建示例 -------- .. code-block:: text 输入:0 -> 0 -> 0 -> 2 -> 2 -> 5 输出:0 -> 2 -> 5 三个 0 保留第一个,两个 2 保留第一个,5 原样保留。 .. code-block:: text 输入:-2 -> -1 -> -1 -> 3 -> 3 -> 3 -> 8 输出:-2 -> -1 -> 3 -> 8 每个连续值段都压缩为一个原节点。 .. code-block:: text 输入:空链表 输出:空链表 没有节点时直接返回空指针。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: ListNode* setBased(ListNode* head) { std::unordered_set 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)`` 额外空间,也忽略了本题最关键的有序结构。 连续值段 ~~~~~~~~ 链表按非递减顺序排列,所以相同值必然连续出现。链表可以分成若干值段: .. code-block:: text 0 -> 0 -> 0 | 2 -> 2 | 5 每段只需保留第一个节点,并让它直接连接到下一段的第一个节点。进入更大的值后,当前值不会再次出现, 因此不需要集合或全局计数。 递归压缩 ~~~~~~~~ 递归方法先去重 ``head->next`` 开始的后缀,再检查处理后的后继是否与 ``head`` 同值。若同值,就持续绕过这些节点。 后缀已经保证每个值至多保留一次,所以递归返回后通常只需一次比较;代码保留 ``while``,使局部逻辑独立且更容易验证。 递归层数最多为节点数,因此需要 ``O(n)`` 调用栈。 单指针状态 ~~~~~~~~~~ 迭代方法让 ``current`` 始终指向当前值段保留的第一个节点。每轮外层循环开始时: - 从链表头到 ``current`` 的部分已经去重; - ``current`` 本身必须保留; - ``current->next`` 开始仍可能包含同值节点。 只要后继与 ``current`` 同值,就执行: .. code-block:: cpp current->next = current->next->next; 这会绕过一个重复节点,同时保持 ``current`` 不动,以便继续检查新的后继。 连续绕过 ~~~~~~~~ 输入 ``1 -> 1 -> 1 -> 2`` 时,删除第一个重复后,``current->next`` 仍然是 1。若只使用一次 ``if``, 第三个 1 会被错误保留。因此必须使用内层 ``while``,直到后继为空或值发生变化。 .. list-table:: :header-rows: 1 * - ``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)``。