0143. Reorder List ================== 题目信息 -------- :题号: 0143. 重排链表 :难度: Medium :主题: 链表、快慢指针、反转链表、交替合并 :原题: `LeetCode 0143 `_ :重点: 将首尾交替的随机访问需求分解为找中点、反转后半段和双链交织,并保持节点集合与无环性 题目重述 -------- 给定单链表 ``L0 -> L1 -> ... -> Ln``,原地重排为 ``L0 -> Ln -> L1 -> L(n-1) -> L2 -> L(n-2) -> ...``。只能修改已有节点的 ``next`` 指针,不得修改 节点值,也不得用新节点替换原节点。函数直接修改输入链表,无需返回头节点。 自建示例 -------- * ``8 -> 3 -> 5 -> 1 -> 9`` 重排为 ``8 -> 9 -> 3 -> 1 -> 5``,奇数长度的中间节点 ``5`` 留在 最后; * ``4 -> 7 -> 2 -> 6`` 重排为 ``4 -> 6 -> 7 -> 2``,偶数长度两半各含两个节点; * 空链、单节点链和双节点链的相对顺序都无需改变。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: void reorderWithNodeArray(ListNode* head) { std::vector nodes; for (ListNode* node = head; node != nullptr; node = node->next) { nodes.push_back(node); } if (nodes.empty()) { return; } int left = 0; int right = static_cast(nodes.size()) - 1; while (left < right) { nodes[left]->next = nodes[right]; ++left; if (left == right) { break; } nodes[right]->next = nodes[left]; --right; } nodes[left]->next = nullptr; } ListNode* reverseList(ListNode* head) { ListNode* reversed = nullptr; while (head != nullptr) { ListNode* next = head->next; head->next = reversed; reversed = head; head = next; } return reversed; } void splitReverseAndMerge(ListNode* head) { if (head == nullptr || head->next == nullptr) { return; } ListNode* slow = head; ListNode* fast = head; while (fast->next != nullptr && fast->next->next != nullptr) { slow = slow->next; fast = fast->next->next; } ListNode* second = slow->next; slow->next = nullptr; second = reverseList(second); ListNode* first = head; while (second != nullptr) { ListNode* nextFirst = first->next; ListNode* nextSecond = second->next; first->next = second; second->next = nextFirst; first = nextFirst; second = nextSecond; } } public: void reorderList(ListNode* head) { splitReverseAndMerge(head); } }; 题解 ---- 原始困难来自单链表没有向前指针 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 目标顺序要求交替取得最左、最右尚未使用的节点。数组可以用两个下标完成,但单链表从 ``Ln`` 无法直接走回 ``L(n-1)``。最直观的 ``reorderWithNodeArray`` 先把所有节点地址放进数组,再用左右下标重连;它不复制 节点,只额外保存 ``O(n)`` 个指针。 数组方案还暴露了一个必要动作:最后必须把尾节点 ``next`` 设为空。旧链中的边在重连过程中并非全部自动 消失,遗漏断尾可能让最终节点仍指向已放到前面的节点,形成环。 怎样把“倒序取后半段”变成顺序访问 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 目标序列的后半部分按 ``Ln, L(n-1), ...`` 消耗。若先把链表切成前后两段,再原地反转后半段,两个待合并 序列都可以只沿 ``next`` 向前读取: .. code-block:: text 原链: L0 -> L1 -> L2 -> L3 -> L4 切分: L0 -> L1 -> L2 L3 -> L4 反转后半: L0 -> L1 -> L2 L4 -> L3 交替合并: L0 -> L4 -> L1 -> L3 -> L2 这个结构信息把节点数组承担的随机访问工作,转换成三次线性指针操作。 中点为何这样选择 ~~~~~~~~~~~~~~~~ ``slow``、``fast`` 都从头开始,快指针每轮走两步。循环要求 ``fast->next`` 和 ``fast->next->next`` 都存在,因此停止时 ``slow`` 位于前半段最后一个节点: * 奇数长度 ``5``:``slow`` 停在下标 ``2``,前半段三节点、后半段两节点; * 偶数长度 ``4``:``slow`` 停在下标 ``1``,两段各两节点。 让奇数长度的前半段多一个节点,正好使唯一中间节点最后留在第一链尾部。取出 ``second = slow->next`` 后 立即写 ``slow->next = nullptr``,把两段彻底断开;这既给前半段建立尾部,也保证后续反转和合并面对两条 互不相交的有限链。 反转阶段保存的状态 ~~~~~~~~~~~~~~~~~~ ``reverseList`` 每次改写当前节点 ``next`` 前,先用 ``next`` 保存尚未处理的原后继;``reversed`` 始终是 已经反转好的前缀头。若先改指针再保存后继,剩余后半链会丢失。反转不创建或删除节点,只改变第二段内部 边的方向。 合并时为何必须先保存两条后继 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 每轮要把 ``first -> nextFirst`` 和 ``second -> nextSecond`` 改成 ``first -> second -> nextFirst``。一旦写入新边,原后继就可能不再可达,所以代码先保存 ``nextFirst``、``nextSecond``,完成两次连接后再让两个游标各自前进。 .. list-table:: :header-rows: 1 * - 合并前待处理头 - 本轮新边 - 下一轮待处理头 * - ``first=L0``、``second=L4`` - ``L0 -> L4 -> L1`` - ``first=L1``、``second=L3`` * - ``first=L1``、``second=L3`` - ``L1 -> L3 -> L2`` - 第二链为空,停止 后半段长度永远不超过前半段,所以以 ``second != nullptr`` 为循环条件时,``first`` 一定存在。偶数长度在 最后一轮连接到 ``nextFirst == nullptr``;奇数长度则连接到剩余中间节点,而它已因切分成为空尾。 为什么没有节点丢失、重复或成环 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 切分后两段节点集合互斥且并集为原节点集合;反转只重排第二段;合并每轮从第二段消费一个节点并插入第一段 相邻位置,没有创建或复用额外节点。两段在合并前都以空结束,且游标只向各自未处理后缀前进,最终连接也 落到未消费节点或空指针,因此不会形成回边。 主解选择与复杂度 ~~~~~~~~~~~~~~~~ 公开入口采用切分、反转、合并。三阶段各为线性扫描,总时间 ``O(n)``,只维护固定数量指针,额外空间 ``O(1)``。节点数组方案同样清楚且时间 ``O(n)``,但需 ``O(n)`` 指针空间;保留它作为首尾访问需求的直接 基线,主解则利用“后半段只需要倒序读取”删除整张索引表。