CodeBrick 博客

Appearance

2019·41 链表重排：从数组辅助到三步原地 ​

本文是「从暴力解到最优解」专题的第二篇。这道题和 2018·41 的分差来源相反：那道卡的是时间，这道卡的是空间——题面直接把 O(1) 空间写成了硬性约束。

题目 ​

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

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

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

(1) 给出算法的基本设计思想。 (2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。 (3) 说明你所设计算法的时间复杂度。

总分 10 分。注意题面同时给了两个约束：空间 O(1) 是硬性写死的，时间「尽可能高效」。

第一步：最自然的想法——数组辅助 ​

L' 的形态是「从两端向中间交替取」：先 a₁、再 aₙ、再 a₂、再 aₙ₋₁……如果这是数组题，两端下标 i、j 交替向中间靠拢就完事了。麻烦在于它是单链表——aₙ 在链表里恰恰是最难够到的。

最自然的补救：把链表结点指针全存进一个数组，用数组换来随机访问能力，然后按 L' 的顺序重新接 next 指针：

c
void rearrange(NODE *L) {
    // 数一遍结点个数
    int n = 0;
    for (NODE *p = L->next; p != NULL; p = p->next) n++;
    if (n < 3) return;                          // 0/1/2 个结点无需重排

    // 把所有结点指针存进数组，换来随机访问
    NODE **nodes = (NODE **)malloc(n * sizeof(NODE *));
    int k = 0;
    for (NODE *p = L->next; p != NULL; p = p->next) nodes[k++] = p;

    // 两端下标交替向中间靠拢，按 L' 顺序重接 next
    int i = 0, j = n - 1;
    while (i < j) {
        nodes[i]->next = nodes[j];              // a(i+1) -> a(j+1)
        nodes[j]->next = nodes[i + 1];          // a(j+1) -> 下一个左端元素
        i++;
        j--;
    }
    nodes[i]->next = NULL;                      // 中间结点收尾
    free(nodes);
}

拿 n=6 走一遍：i=0, j=5 接出 a₁→a₆→a₂；i=1, j=4 接出 a₂→a₅→a₃；i=2, j=3 接出 a₃→a₄；退出循环后 a₄ 收尾置 NULL。结果 a₁,a₆,a₂,a₅,a₃,a₄ ✓。奇数长度 n=5 时退出循环的是 i=j=2，a₃ 收尾 ✓。

复杂度：数结点 + 存数组 + 重接，三段线性，时间 O(n)；指针数组占 O(n) 空间。

时间已经达标了，卡在空间上。

它值多少分 ​

按正确性/最优性两个维度（详见总纲）：

  • 正确性：这份解设计思想清楚（两端交替取）、代码能正确得到 L'、奇偶长度都处理对了——正确性维度的主体分拿得到。
  • 最优性：题面把 O(1) 空间写成了硬性要求，O(n) 的指针数组直接违反它，空间相关的分拿不到。

还有一条路线也值得知道：不开数组、每轮从当前位置向后扫到尾把尾结点摘下来接到前面——空间 O(1) 满足硬约束，但时间退化到 O(n2)，「时间上尽可能高效」那档同样拿不到。两条暴力路线殊途同归：正确性大头在手，最优性档丢掉。

对这道 10 分的题来说，暴力解保底、分差有限——但这道题的最优解三步全是链表基本功，值得练到能拿满。

差距在哪：数组买来的能力，链表自己就有 ​

数组辅助解花 O(n) 空间买了一样东西：随机访问。但审视一下 L' 的构造过程，它真正用到的访问模式只有两种：

  • 左半边 a₁, a₂, a₃, …——从头顺序访问。链表本来就会。
  • 右半边 aₙ, aₙ₋₁, aₙ₋₂, …——从尾逆序访问。链表不会，这才是花钱买数组的真实原因。

所以浪费点找到了：为了「逆序访问后一半」这一个需求，把整条链表都搬进了数组。而「让链表的后一半支持逆序访问」有零成本的做法——就地逆置。后半截反转之后，「逆序访问原后半」变成了「顺序访问新链」，随机访问的需求彻底消失。

智慧化改造：三步原地 ​

于是最优解自然浮现，三步全是改指针，一个新结点都不分配：

  1. 快慢指针找中点——slow 每步走 1、fast 每步走 2，fast 到尾时 slow 正好在前半最后一个结点，把链表切成前后两半；
  2. 后半就地逆置——三指针反转（prev/cur/nxt），aₙ 成为后半新头；
  3. 交叉合并——前半指针 p、逆置后的后半指针 r 交替编织。
c
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;                           // 逆置后的新头（即原 an）

    // ③ 交叉合并：r 的结点逐个插到前半的间隙里
    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 = p_nxt;
        r = r_nxt;
    }
}

复杂度：找中点、逆置、合并各扫半条链，时间 O(n)；全程只有固定几个指针变量，空间 O(1)。两个约束同时达标，这就是标准答案。

从数组辅助解升级过来，四个细节决定这 10 分能拿多满：

  • 快慢指针的循环条件必须是 fast->next != NULL && fast->next->next != NULL。写成 fast != NULL && fast->next != NULL 会让 slow 多走一步，奇数长度时切分点偏右、前后半颠倒。
  • 先切断再逆置：slow->next = NULL 必须发生在反转之前，否则前后两半在反转过程中纠缠不清。
  • 合并时先存后继再改指针：p_nxt、r_nxt 必须先保存——p->next = r 一执行，原来的后继就找不回来了。这和逆置的三指针是同一个肌肉记忆。
  • 前半 ≥ 后半是隐含不变量：偶数长度两半相等，奇数长度前半多一个。合并循环里 r 先耗尽，剩下的前半尾结点连接已经就位，无需额外收尾。

两版对照跑一遍 ​

同一条链 1 → 2 → 3 → 4 → 5 → 6，目标 1 → 6 → 2 → 5 → 3 → 4。先看数组辅助版（演示为不带头结点的等价 JavaScript 版本）：

加载可视化中...

再看三步原地版——注意全程只有指针在动，没有任何新容器出现：

加载可视化中...

演示为不带头结点的 JavaScript 等价版本；考卷上请按题面用带头结点写法（上文 C 代码）。

下一步 ​

相关真题（1题）

2017Q11选择题2分
去刷题

链式存储排序：链式存储对各排序算法效率的影响

单链表