考研笔记

板子：链表重排（2019）

把 重排成 ，要求空间 。拆成三个已经会的板子：① 快慢指针找中点 → ② 就地逆置后半段 → ③ 两段交替合并。

代码

void reorder(LinkList h) {                   // 2019：(a1,a2,…,an) → (a1,an,a2,an-1,…)
    LNode *p = h, *q = h, *r, *s;
    // ① 找中点：从头结点出发，p 最后停在第 ⌈n/2⌉ 个结点
    while (q != NULL && q->next != NULL) {
        p = p->next;                         // p 走一步
        q = q->next->next;                   // q 走两步
    }
    // ② 把 p 后面的部分就地逆置：p 当头结点，逐个头插
    q = p->next;                             // q：后半段的第一个结点
    p->next = NULL;
    while (q != NULL) {
        r = q->next;                         // 先保存后继
        q->next = p->next;
        p->next = q;
        q = r;
    }
    // ③ 前半段从 s 开始，后半段从 q 开始，把后半段的结点逐个插到 s 后面
    s = h->next;
    q = p->next;
    p->next = NULL;                          // 在 p 处断开，前半段以 p 结尾
    while (q != NULL) {
        r = q->next;                         // 保存后半段的下一个
        q->next = s->next;                   // q 插到 s 后面
        s->next = q;
        s = q->next;                         // s 跳到前半段的下一个结点
        q = r;
    }
}

复杂度：三步各扫一遍，时间 ，空间 。

例：1 2 3 4 5 → 中点是 3 → 逆置后变成 1 2 3 | 5 4 → 交替合并得到 1 5 2 4 3。

关键边界：中点为什么要停在第 ⌈n/2⌉ 个

前半段有 个结点，后半段有 个，前半段不会比后半段短。第③步把后半段的结点逐个插进前半段，前半段就不会先用完，s 不会变成 NULL 以后还被访问。

所以第①步必须从头结点 h 出发，循环条件是 q != NULL && q->next != NULL。如果从 h->next 出发，偶数长度时会停在后一个中点，两段的长度就对不上了（见 快慢指针的中点表）。

易错点

  • 第②步开始前要 p->next = NULL，否则头插会形成环（同 就地逆置 的易错点）。
  • 第③步开始前要再 p->next = NULL 一次，把前半段和后半段断开。
  • 第③步的循环条件看的是后半段的 q，不是前半段的 s。
  • 如果只能想到 空间的做法（把结点存进数组再重连），也是正确解，但题目明确要求空间 ，会扣分。

链接

反向链接