0082. Remove Duplicates from Sorted List II =========================================== 题目信息 -------- :题号: 0082. 删除排序链表中的重复元素 II :难度: Medium :主题: 单链表、有序重复段、哨兵节点 :原题: `LeetCode 0082 `_ :重点: 从统计出现次数,推导到按连续值段处理,再用哨兵节点统一删除头部重复段 题目重述 -------- 给定一个按非递减顺序排列的单链表 ``head``,删除所有出现次数大于 1 的值对应的全部节点。 结果中只能保留在原链表中恰好出现一次的值,并保持这些节点原有的相对顺序。 链表节点数满足 ``0 <= n <= 300``,节点值满足 ``-100 <= Node.val <= 100``。 自建示例 -------- .. code-block:: text 输入:1 -> 1 -> 2 -> 3 -> 3 -> 4 -> 5 -> 5 输出:2 -> 4 值 1、3、5 都属于长度大于 1 的重复段,整段删除;值 2、4 各出现一次,保留原节点。 .. code-block:: text 输入:2 -> 2 -> 2 输出:空链表 链表只有一个值段,且该段长度为 3,因此没有节点可以保留。 .. code-block:: text 输入:1 -> 2 -> 3 输出:1 -> 2 -> 3 所有值段长度都为 1,原链表保持不变。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: ListNode* countAndRelink(ListNode* head) { std::unordered_map frequency; for (ListNode* node = head; node != nullptr; node = node->next) { ++frequency[node->val]; } ListNode dummy(0); ListNode* tail = &dummy; ListNode* current = head; while (current != nullptr) { ListNode* next = current->next; if (frequency[current->val] == 1) { tail->next = current; tail = current; tail->next = nullptr; } current = next; } return dummy.next; } ListNode* recursiveSkip(ListNode* head) { if (head == nullptr || head->next == nullptr) { return head; } if (head->val != head->next->val) { head->next = recursiveSkip(head->next); return head; } int duplicate_value = head->val; while (head != nullptr && head->val == duplicate_value) { head = head->next; } return recursiveSkip(head); } ListNode* sentinelScan(ListNode* head) { ListNode dummy(0, head); ListNode* previous = &dummy; ListNode* current = head; while (current != nullptr) { if (current->next != nullptr && current->val == current->next->val) { int duplicate_value = current->val; while (current != nullptr && current->val == duplicate_value) { current = current->next; } previous->next = current; } else { previous = current; current = current->next; } } return dummy.next; } public: ListNode* deleteDuplicates(ListNode* head) { return sentinelScan(head); } }; 解题推导 -------- 从节点计数到值段 ~~~~~~~~~~~~~~~~ 最直接的方法是先统计每个值的出现次数,再扫描链表,只把频次为 1 的节点重新连接到结果链表。 这种方法容易验证,但需要 ``O(n)`` 额外空间,而且没有利用链表已经有序这一条件。 有序链表中,相同值必然连续出现。因此不必保存所有值的全局频次,只需把链表划分为连续值段: - 值段长度为 1,保留该节点; - 值段长度大于 1,绕过整段节点。 递归按值段处理 ~~~~~~~~~~~~~~ 递归方法直接处理当前值段。若头节点与后继值不同,当前值段只有一个节点,可以保留头节点, 再递归过滤后缀。若两者相同,就先移动到第一个不同值,再从该位置继续递归。 每次递归至少处理一个节点,因此最终一定到达空链表。它完整表达了值段分类,但递归深度最坏为 ``O(n)``,还可以改为迭代扫描。 哨兵节点统一边界 ~~~~~~~~~~~~~~~~ 重复段可能出现在链表头部,例如 ``1 -> 1 -> 2``。没有哨兵时,删除头部重复段需要额外修改 ``head``。建立 ``dummy.next = head`` 后,``previous`` 始终指向结果有效前缀的最后一个节点, 所有删除都统一为: .. code-block:: text previous->next = current 其中 ``current`` 已移动到重复段之后。即使首个值段被删除,修改的仍然只是 ``dummy.next``。 前驱指针不变量 ~~~~~~~~~~~~~~ 每轮开始时: - ``dummy.next`` 到 ``previous`` 是已经确认应保留的有效前缀; - ``current`` 指向尚未分类的第一个节点; - ``previous->next == current``。 若 ``current`` 与后继值不同,由于链表非递减,该值不可能在后方再次出现,当前节点可以保留。 此时同时推进 ``previous`` 和 ``current``。 若两者值相同,``current`` 所在值段必然重复。算法只推进 ``current``,直到离开该值段, ``previous`` 保持不动,再把它直接连接到新的 ``current``。因此重复段中不会留下任何节点。 .. list-table:: :header-rows: 1 * - 未处理后缀 - ``previous`` - 动作 * - ``1,2,3,3,4,4,5`` - ``dummy`` - 1 唯一,前驱推进到 1 * - ``2,3,3,4,4,5`` - 1 - 2 唯一,前驱推进到 2 * - ``3,3,4,4,5`` - 2 - 越过全部 3,连接到第一个 4 * - ``4,4,5`` - 2 - 越过全部 4,连接到 5 * - ``5`` - 2 - 5 唯一,保留 结果与资源 ~~~~~~~~~~ 每个连续值段恰好被分类一次。长度为 1 的段进入有效前缀,长度大于 1 的段被前驱整段绕过, 所以结果恰好包含所有只出现一次的值,并保持原有顺序。 代码只修改节点的 ``next`` 指针,不创建结果节点。被绕过节点的释放策略由调用环境决定; LeetCode 的接口不要求在函数内手动释放这些节点。 复杂度 ~~~~~~ 哈希计数方法时间 ``O(n)``、额外空间 ``O(n)``。递归方法时间 ``O(n)``、调用栈 ``O(n)``。 哨兵迭代方法中每个节点最多被访问常数次,时间 ``O(n)``,额外空间 ``O(1)``。