题目

设线性表 L = (a₁, a₂, a₃, …, aₙ₋₂, aₙ₋₁, aₙ) 采用带头结点的单链表保存，链表中的结点定义如下：

typedef struct node {
    int data;
    struct node *next;
} NODE;

请设计一个空间复杂度为 O(1) 且时间上尽可能高效的算法，重新排列 L 中的各结点，得到线性表 L' = (a₁, aₙ, a₂, aₙ₋₁, a₃, aₙ₋₂, …)。要求：

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

(3) 说明你所设计算法的时间复杂度。

解析

(1) 设计思想

答案：三步原地操作——快慢指针找中点把链表切成左右两半 → 右半就地逆置 → 左右两半交叉合并。整个过程只用常数辅助变量，O(n) 时间、O(1) 空间。

为什么需要这三步？

目标 L' = (a₁, aₙ, a₂, aₙ₋₁, a₃, aₙ₋₂, …) 把"前一半"与"后一半的逆序"交叉编织。三步分别解决：

1. 找中点——单链表无随机访问，要把"后一半"分出来，必须先定位中点。快慢指针（fast 走两步、slow 走一步）让 slow 在 fast 走到尾时正好位于中点；
2. 逆置后半——后半要从 aₙ 开始消费（再 aₙ₋₁ ... ），原顺序是从前往后，必须就地反转指针方向，让 aₙ 变成新链头；
3. 交叉合并——同时维护左半的指针 p、逆后右半的指针 r，循环：让 p 的 next 指向 r、r 的 next 指向 p 的原 next，p、r 同步前移；O(n) 一遍完成。

中点切分的细节：

• L 为带头结点链表，slow 从头结点出发；
• 偶数长度（n=6，L: head → 1→2→3→4→5→6）：slow 终止在 a₃，前半为 1,2,3，后半为 4,5,6；
• 奇数长度（n=5，head → 1→2→3→4→5）：slow 终止在 a₃，前半为 1,2,3（包含中位），后半为 4,5。

不管奇偶，前半 ≥ 后半，合并完一定先取尽后半再以前半的最后元素结尾，自然吻合 L' 形态。

(2) 代码实现

typedef struct node {
    int data;
    struct node *next;
} NODE;

void rearrange(NODE *L) {
    if (L == NULL || L->next == NULL || L->next->next == NULL) return;

    // ① 快慢指针找中点：slow 终止在前半最后一个结点
    NODE *slow = L, *fast = L;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // ② 把后半部分截下来并就地逆置
    NODE *q = slow->next;
    slow->next = NULL;                            // 切断
    NODE *prev = NULL, *cur = q, *nxt;
    while (cur != NULL) {
        nxt = cur->next;
        cur->next = prev;                         // 反转指针方向
        prev = cur;
        cur = nxt;
    }
    NODE *r = prev;                               // 逆置后的新头

    // ③ 交叉合并：把 r 的结点逐个插到 L 的奇数位
    NODE *p = L->next;                            // 前半第一个数据结点
    while (p != NULL && r != NULL) {
        NODE *p_nxt = p->next;
        NODE *r_nxt = r->next;
        p->next = r;
        r->next = p_nxt;                          // 若 p_nxt 为 NULL（前半已空），合并自然结束
        p = p_nxt;
        r = r_nxt;
    }
}

关键点说明：

• 找中点的循环条件 fast->next && fast->next->next：确保 fast 走两步不越界；当 fast 在末尾或倒数第二时停下，slow 正好在中点。别写成 fast && fast->next——那样 slow 会多走一步，奇数长度时偏右。
• 逆置必须先 cut 再反转：第二步先把 slow->next = NULL 切断左右两半，再反转后半。如果不切，反转过程中会与左半藕断丝连，逻辑混乱。
• 交叉合并顺序：每一轮先保存 p_nxt、r_nxt，再改指针——否则 p->next = r 后，原来的 p->next 已丢失。
• 不要 malloc 新结点：所有操作都是改指针指向，不分配/释放任何结点，空间复杂度才是真正的 O(1)。

(3) 时间复杂度

• 时间复杂度 ：三段每段都是单趟扫描——找中点 O(n/2)，逆置 O(n/2)，合并 O(n/2)，加起来 O(n)。
• 空间复杂度 ：仅用 slow、fast、prev、cur、nxt、q、r、p、p_nxt、r_nxt 等指针变量，与 n 无关。

编者注（生僻术语）：「快慢指针」（slow/fast pointer）是单链表问题的万能钥匙——找中点、判环、找环入口、找倒数第 k 个结点都靠它。题目要求 O(1) 空间下完成，必须用快慢指针 + 就地逆置；用栈或数组当辅助是 O(n) 空间，会丢分。