0092. Reverse Linked List II ============================ 题目信息 -------- :题号: 0092. 反转链表 II :难度: Medium :主题: 单链表、区间反转、哨兵节点 :原题: `LeetCode 0092 `_ :重点: 从保存节点顺序,推导到固定区间前驱并原地完成局部反转 题目重述 -------- 给定单链表 ``head`` 和两个一基位置 ``left``、``right``,反转第 ``left`` 个节点到第 ``right`` 个节点组成的闭区间,并返回反转后的链表。 区间外节点的相对顺序必须保持不变。链表节点数为 ``1..500``,并保证 ``1 <= left <= right <=`` 链表长度。附加要求是尽量只遍历链表一次。 自建示例 -------- .. code-block:: text 输入:9 -> 8 -> 7 -> 6 -> 5,left = 2,right = 5 输出:9 -> 5 -> 6 -> 7 -> 8 第 2 到第 5 个节点整体逆序,首节点 9 保持原位。 .. code-block:: text 输入:1 -> 2 -> 3 -> 4,left = 1,right = 3 输出:3 -> 2 -> 1 -> 4 反转区间从头节点开始,因此结果链表的头节点发生变化。 .. code-block:: text 输入:3 -> 4 -> 5,left = 2,right = 2 输出:3 -> 4 -> 5 区间长度为 1 时,不需要移动任何节点。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: ListNode* nodeArray(ListNode* head, int left, int right) { std::vector nodes; for (ListNode* node = head; node; node = node->next) { nodes.push_back(node); } std::reverse(nodes.begin() + left - 1, nodes.begin() + right); for (int index = 0; index + 1 < static_cast(nodes.size()); ++index) { nodes[index]->next = nodes[index + 1]; } nodes.back()->next = nullptr; return nodes.front(); } ListNode* reverseAndReconnect(ListNode* head, int left, int right) { ListNode dummy(0, head); ListNode* before = &dummy; for (int position = 1; position < left; ++position) { before = before->next; } ListNode* segment_tail = before->next; ListNode* current = segment_tail; ListNode* previous = nullptr; for (int count = 0; count <= right - left; ++count) { ListNode* next = current->next; current->next = previous; previous = current; current = next; } before->next = previous; segment_tail->next = current; return dummy.next; } ListNode* frontInsertion(ListNode* head, int left, int right) { ListNode dummy(0, head); ListNode* before = &dummy; for (int position = 1; position < left; ++position) { before = before->next; } ListNode* segment_tail = before->next; for (int step = 0; step < right - left; ++step) { ListNode* moved = segment_tail->next; segment_tail->next = moved->next; moved->next = before->next; before->next = moved; } return dummy.next; } public: ListNode* reverseBetween(ListNode* head, int left, int right) { return frontInsertion(head, left, right); } }; 题解 ---- 节点顺序重排 ~~~~~~~~~~~~ 最直接的方法是把所有节点地址保存到数组中,反转下标区间 ``[left-1, right)``,再按数组顺序重建 ``next`` 链接。它把链表问题转成数组区间反转,逻辑直观,额外空间为 ``O(n)``。 链表本身已经提供了全部节点,继续寻找不保存数组的原地做法。 区间的三处连接 ~~~~~~~~~~~~~~ 设 ``before`` 是第 ``left`` 个节点的前驱。局部反转完成后只需保证三部分正确相接: .. code-block:: text 原前缀尾 before | v 反转后的区间头 ... 原区间首节点 segment_tail -> 原后缀头 当 ``left = 1`` 时不存在真实前驱。令 ``dummy.next = head``,则 ``before`` 始终存在,结果头节点也统一从 ``dummy.next`` 返回。 标准局部反转 ~~~~~~~~~~~~ 从 ``before.next`` 开始执行普通链表反转,恰好处理 ``right-left+1`` 个节点。循环结束时: * ``previous`` 指向反转后的区间头; * ``segment_tail`` 是原区间首节点,也是反转后的区间尾; * ``current`` 指向原第 ``right`` 个节点之后的后缀头。 因此只需执行: .. code-block:: text before.next = previous segment_tail.next = current 这种方法先完成整段指针翻转,再恢复区间两端连接。 头插法的局部状态 ~~~~~~~~~~~~~~~~ 还可以固定 ``before`` 与 ``segment_tail``,反复把 ``segment_tail`` 后面的节点摘出并插到区间最前面: .. code-block:: text moved = segment_tail.next segment_tail.next = moved.next moved.next = before.next before.next = moved 每轮开始时,``before.next`` 是当前已反转部分的头,``segment_tail`` 是其尾, ``segment_tail.next`` 是下一个尚未移动的区间节点。 状态演化 ~~~~~~~~ 以 ``1 -> 2 -> 3 -> 4 -> 5``、``left=2``、``right=4`` 为例: .. list-table:: :header-rows: 1 * - 阶段 - 链表 - 下一步移动 * - 初始 - ``1 -> [2 -> 3 -> 4] -> 5`` - 3 * - 第一次 - ``1 -> [3 -> 2 -> 4] -> 5`` - 4 * - 第二次 - ``1 -> [4 -> 3 -> 2] -> 5`` - 完成 区间共有 ``right-left+1`` 个节点。原首节点已经位于局部结构中,其余 ``right-left`` 个节点各执行一次 头插,整段便完成逆序。 连接安全性 ~~~~~~~~~~ 摘出 ``moved`` 时先令 ``segment_tail.next = moved.next``,保留未处理区间和后缀;随后再把 ``moved`` 接到 ``before`` 后面。任何时刻每个节点都只有一个前驱路径,不会丢失节点或形成环。 ``before`` 之前和最终后缀内部的链接从未改变,所以区间外节点的相对顺序保持不变。每个原节点也只被移动或保留一次, 结果中的节点集合与输入完全相同。 复杂度 ~~~~~~ 节点数组方法时间 ``O(n)``、额外空间 ``O(n)``。标准局部反转和头插法都只定位一次区间前驱,并处理 区间内节点一次,时间 ``O(n)``、额外空间 ``O(1)``。