0086. Partition List ==================== 题目信息 -------- :题号: 0086. 分隔链表 :难度: Medium :主题: 单链表、稳定分区、双链拼接 :原题: `LeetCode 0086 `_ :重点: 从保存节点引用,推导到常量空间的稳定双链分区与原链抽取 题目重述 -------- 给定单链表 ``head`` 和整数 ``x``,重新连接原链表节点,使所有值小于 ``x`` 的节点都位于值大于等于 ``x`` 的节点之前。 两个分区内部必须保持原链表中的相对顺序。算法返回重排后的头节点,不要求按数值排序,也不能遗漏或复制节点。 链表节点数在 ``0..200`` 范围内,节点值和 ``x`` 都在 ``-100..100`` 范围内。 自建示例 -------- .. code-block:: text 输入:5 -> 1 -> 4 -> 2 -> 3,x = 4 输出:1 -> 2 -> 3 -> 5 -> 4 小于 4 的节点按原顺序形成 ``1,2,3``,其余节点按原顺序形成 ``5,4``。 .. code-block:: text 输入:1 -> 4 -> 2 -> 5 -> 3,x = 3 输出:1 -> 2 -> 4 -> 5 -> 3 前段保留 ``1,2`` 的顺序,后段也保留 ``4,5,3`` 的顺序。 .. code-block:: text 输入:1 -> 2,x = 5 输出:1 -> 2 所有节点都属于前一分区,拼接后链表不变。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: ListNode* collectReferences(ListNode* head, int x) { std::vector before; std::vector after; for (ListNode* node = head; node; node = node->next) { if (node->val < x) { before.push_back(node); } else { after.push_back(node); } } ListNode dummy(0); ListNode* tail = &dummy; for (ListNode* node : before) { tail->next = node; tail = node; } for (ListNode* node : after) { tail->next = node; tail = node; } tail->next = nullptr; return dummy.next; } ListNode* inPlaceSplice(ListNode* head, int x) { ListNode dummy(0, head); ListNode* lessTail = &dummy; while (lessTail->next && lessTail->next->val < x) { lessTail = lessTail->next; } ListNode* scanPrev = lessTail; while (scanPrev->next) { if (scanPrev->next->val >= x) { scanPrev = scanPrev->next; continue; } ListNode* moved = scanPrev->next; scanPrev->next = moved->next; moved->next = lessTail->next; lessTail->next = moved; lessTail = moved; } return dummy.next; } ListNode* stableTwoLists(ListNode* head, int x) { ListNode beforeDummy(0); ListNode afterDummy(0); ListNode* beforeTail = &beforeDummy; ListNode* afterTail = &afterDummy; while (head) { ListNode* next = head->next; head->next = nullptr; if (head->val < x) { beforeTail->next = head; beforeTail = head; } else { afterTail->next = head; afterTail = head; } head = next; } beforeTail->next = afterDummy.next; return beforeDummy.next; } public: ListNode* partition(ListNode* head, int x) { return stableTwoLists(head, x); } }; 题解 ---- 稳定分区模型 ~~~~~~~~~~~~ 题目只要求按条件分为两组,不要求组内排序。交换节点值或把小节点不断插到链表头部,都会改变同一分区中的 相对顺序。稳定做法是按原链表的扫描顺序,把节点追加到对应分区的尾部。 引用数组 ~~~~~~~~ 最直接的方法把小于 ``x`` 和大于等于 ``x`` 的节点引用分别保存到两个数组,再按两个数组的顺序重连。 这种方法容易验证稳定性,但需要 ``O(n)`` 额外空间。 双链尾插 ~~~~~~~~ 数组只承担“记住两个分区顺序”的作用。链表自身已经有顺序,因此可以用两组哨兵和尾指针直接构造: * ``beforeTail`` 指向小于 ``x`` 分区的尾节点; * ``afterTail`` 指向大于等于 ``x`` 分区的尾节点; * 当前节点只会被追加到其中一条链。 每条链始终在尾部追加,所以同一分区中的节点顺序与输入一致。 断开旧链接 ~~~~~~~~~~ 处理当前节点前先保存原后继,再把当前节点的 ``next`` 置空: .. code-block:: text next = current.next current.next = null append current current = next 旧 ``next`` 指向尚未分类的混合后缀。提前断开可保证两条临时链都只包含已经分类的节点,也避免最终拼接后 残留旧链接形成错误跨接或环。 状态演进 ~~~~~~~~ 以 ``5 -> 1 -> 4 -> 2 -> 3``、``x = 4`` 为例: .. list-table:: :header-rows: 1 * - 读取节点 - 小于 ``x`` - 大于等于 ``x`` * - 5 - 空 - ``5`` * - 1 - ``1`` - ``5`` * - 4 - ``1`` - ``5 -> 4`` * - 2 - ``1 -> 2`` - ``5 -> 4`` * - 3 - ``1 -> 2 -> 3`` - ``5 -> 4`` 扫描结束后执行 ``beforeTail->next = afterDummy.next``,结果即为两条稳定链的连接。 原链抽取 ~~~~~~~~ ``inPlaceSplice`` 不建立两条独立链。它先让 ``lessTail`` 越过开头已经连续满足 ``val < x`` 的节点,随后 从后缀中逐个抽取小节点,并插到 ``lessTail`` 之后。 ``scanPrev`` 只在当前后继属于后分区时推进;遇到小节点时,先从原位置摘除,再追加到小节点前缀尾部。 抽取顺序就是扫描顺序,因此前后两个分区都保持稳定。 节点守恒 ~~~~~~~~ 每个原节点恰好被扫描一次,并根据互斥条件 ``val < x`` 进入一个分区。算法只修改 ``next``,不复制、删除 或新建结果数据节点。最终拼接后,全部原节点各出现一次。 复杂度来源 ~~~~~~~~~~ 引用数组方法时间 ``O(n)``、额外空间 ``O(n)``。双链尾插和原链抽取都只扫描链表一次,时间 ``O(n)``, 除固定数量的哨兵和指针外不使用额外存储,工作空间 ``O(1)``。