你好，同学。欢迎来到数据结构专题训练。

今天我们要探讨的是链表操作的综合应用题：重排链表。这道题在 LeetCode 上是经典，但在 NOI 竞赛视角下，它是考查指针操作熟练度、空间复杂度控制以及逻辑严密性的极佳素材。

---

一、 预备知识点

在挑战本题前，请确保你已经掌握以下“链表三板斧”：

1. 快慢指针 (Fast & Slow Pointers)：用于寻找链表的中点。
2. 链表原地逆置 (Reverse Linked List)：通过迭代方式改变指针方向，不使用额外空间。
3. 链表合并 (Merge Linked Lists)：按照特定规则交替连接两个链表的节点。

---

二、 NOI 竞赛题目描述

题目名称：重排链表 (Reorder List) 时间限制：1.0s 内存限制：256MB

【问题描述】 给定一个单链表 $L$ 的头节点 $head$，单链表定义为： $L_0 \to L_1 \to \dots \to L_{n-1} \to L_n$

请将其重新排列后变为： $L_0 \to L_n \to L_1 \to L_{n-1} \to L_2 \to L_{n-2} \dots$

【要求】

1. 你不能只是单纯地改变节点内部的值，而是需要实际地进行节点交换和连接。
2. 尽量在不使用额外 $O(n)$ 空间（如数组存储节点）的情况下完成。

【输入格式】 第一行包含一个整数 $N$，表示链表节点个数。 第二行包含 $N$ 个整数，表示链表从头到尾的元素值。

【输出格式】 输出一行，包含 $N$ 个整数，表示重排后的链表元素值。

【样例输入 1】

4
1 2 3 4

【样例输出 1】

1 4 2 3

【样例输入 2】

5
1 2 3 4 5

【样例输出 2】

1 5 2 4 3

【数据规模与约定】

• $1 \le N \le 50,000$
• $1 \le 节点值 \le 1000$

---

三、 启发式思路引导：草稿纸上的推演

观察目标序列：$L_0, L_n, L_1, L_{n-1} \dots$。你会发现这实际上是原链表的前半段与逆序后的后半段交替合并的结果。

请在草稿纸上按以下步骤进行图形推导：

第一步：寻找中点

利用快慢指针，快指针走两步，慢指针走一步。

• 对于 1-2-3-4-5，慢指针最终停在 3。
• 动作：以 3 为界，将链表断开为 1-2-3 和 4-5。

第二步：翻转后半部分

将 4-5 翻转为 5-4。

• 思考：为什么要做这一步？因为目标序列需要从末尾取元素，而单链表无法从后往前走。

第三步：交替合并

将 1-2-3 与 5-4 依次连接。

1. 取 1，接 5。
2. 取 2，接 4。
3. 取 3。 结果：1-5-2-4-3。

---

四、 算法流程图（伪代码逻辑）

在 Mermaid 流程图中，我们用 Node_X 代表节点指针，避免使用特殊符号。

graph TD
    Start{开始重排} --> CheckEmpty{head 为空或单节点}
    CheckEmpty -- 是 --> Finish(直接返回)
    CheckEmpty -- 否 --> FindMid(使用快慢指针寻找链表中点)
    
    FindMid --> Split(将链表从中点处断开为两个子链表 L1 和 L2)
    Split --> Reverse(原地翻转链表 L2)
    
    Reverse --> MergeInit(初始化两个指针 p1 指向 L1, p2 指向 L2)
    MergeInit --> MergeLoop{p2 是否为空}
    
    MergeLoop -- 是 --> Finish
    MergeLoop -- 否 --> Step1(暂存 p1 和 p2 的后继节点 next1 和 next2)
    Step1 --> Step2(将 p1 的 next 指向 p2)
    Step2 --> Step3(如果 next1 为空则停止, 否则将 p2 的 next 指向 next1)
    Step3 --> Step4(更新 p1 等于 next1, p2 等于 next2)
    Step4 --> MergeLoop

---

五、 复杂度分析与优化建议

• 时间复杂度：
  1. 找中点：$O(n)$
  2. 翻转链表：$O(n/2)$
  3. 交替合并：$O(n/2)$
  • 总结：总时间复杂度为 $O(n)$。
• 空间复杂度：
  • 方案 A（数组法）：通过 std::vector 存储节点指针，空间复杂度 $O(n)$。在 $N=50,000$ 时，占用约 400KB 内存，NOI 256MB 绰绰有余。
  • 方案 B（原地指针法）：仅需常数个指针变量，空间复杂度 $O(1)$。在内存受限的极值情况下，此方案是必考点。

优化建议： 在考场上，如果时间充裕，优先写指针法以展示基本功；如果逻辑卡壳，迅速改用数组辅助法，因为 NOI 评测更看重结果的正确性。

---

六、 读题关键词总结

当你在竞赛题目中看到以下描述时，应联想到本题技巧：

1. “不能只改变节点的值”：排除掉数据交换的暴力解，强制考查指针重连。
2. “交替重排 / 镜像重叠”：提示需要寻找中点并翻转后半段。
3. “原地操作”：暗示空间复杂度应为 $O(1)$。

教练寄语：指针操作最怕“断链”或“环链”。写完合并逻辑后，一定要手动模拟一遍 $N$ 为奇数和偶数的情况，确保最后一个节点的 next 指针被正确置为 NULL。