AC215-将单链表 L(a1, a2, ..., an) 重新排列为 (a1, an, a2, an-1, ...)

代码实现

// 函数 func：将单链表 L(a1, a2, ..., an) 重新排列为 (a1, an, a2, an-1, ...)
void func(LinkList L) {
    // 第一步：使用快慢指针找到链表的中点
    LinkList slow = L, fast = L; // slow 为慢指针，fast 为快指针

    // 快慢指针遍历：fast 每次移动两步，slow 每次移动一步
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;      // slow 移动一步
        fast = fast->next->next; // fast 移动两步
    }
    // 循环结束时，slow 指向链表的中点（对于偶数长度指向中间偏左，奇数长度指向中间）

    // 第二步：将链表从中间断开，并逆置后半部分
    LinkList p = slow->next;    // p 指向后半部分的第一个节点
    slow->next = NULL;          // 将前半部分与后半部分断开

    // 第三步：逆置后半部分链表
    while (p != NULL) {
        LinkList r = p->next;   // 保存 p 的后继节点
        p->next = slow->next;   // 将 p 插入到 slow 节点之后
        slow->next = p;         // 完成插入操作
        p = r;                  // 移动 p 到下一个待处理节点
    }
    // 逆置完成后，slow->next 指向原来后半部分的最后一个节点（现在是第一个节点）

    // 第四步：将逆置后的后半部分链表插入到前半部分链表中
    LinkList mid = slow->next;  // mid 指向逆置后的后半部分链表的第一个节点
    slow->next = NULL;          // 再次断开，确保前半部分独立
    LinkList beg = L->next;     // beg 指向原链表第一个数据节点

    // 第五步：交替插入节点
    while (mid != NULL) {
        LinkList r = mid->next;     // 保存 mid 的后继节点
        mid->next = beg->next;      // 将 mid 节点插入到 beg 节点之后
        beg->next = mid;            // 完成插入操作
        beg = mid->next;            // 移动 beg 到下一个插入位置
        mid = r;                    // 移动 mid 到下一个待插入节点
    }
}

---

代码逻辑解析

1. 算法总体思路

将链表重新排列的过程分为五个步骤： 1. 找到链表中点 2. 断开链表 3. 逆置后半部分 4. 交替插入两个链表的节点

2. 第一步：快慢指针找中点

// 快慢指针技巧
while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
}

- fast 指针每次移动两步，slow 指针每次移动一步 - 当 fast 到达链表末尾时，slow 正好在链表中点

3. 第二步：断开链表

LinkList p = slow->next;  // 保存后半部分的起始节点
slow->next = NULL;        // 断开链表

4. 第三步：逆置后半部分

使用头插法逆置链表：

while (p != NULL) {
    LinkList r = p->next;   // 保存下一个节点
    p->next = slow->next;   // 插入到 slow 节点后
    slow->next = p;
    p = r;
}

5. 第四步：交替插入

将逆置后的后半部分节点交替插入到前半部分中。

---

时间复杂度分析

• 找中点：O(n/2) = O(n)
• 逆置后半部分：O(n/2) = O(n)
• 交替插入：O(n/2) = O(n)

因此，总时间复杂度为 O(n)

---

空间复杂度分析

• 额外空间使用：只使用了常量级别的额外变量（slow, fast, p, r, mid, beg）
• 递归调用：没有使用递归

因此，空间复杂度为 O(1)

---

较难理解部分的说明

1. 快慢指针找中点的原理

偶数长度链表：

链表：1 -> 2 -> 3 -> 4 -> NULL
步骤：
初始：slow=1, fast=1
步骤1：slow=2, fast=3  
步骤2：slow=3, fast=NULL
结果：slow 指向第 3 个节点（中点偏右）

奇数长度链表：

链表：1 -> 2 -> 3 -> 4 -> 5 -> NULL
步骤：
初始：slow=1, fast=1
步骤1：slow=2, fast=3
步骤2：slow=3, fast=5
步骤3：slow=4, fast=NULL
结果：slow 指向第 4 个节点（正中间）

2. 逆置链表的过程图解

假设后半部分链表为：3 -> 4 -> 5 -> NULL

初始状态：
slow -> 2 -> 3 -> 4 -> 5 -> NULL
         p

第一次循环：
slow -> 2 -> 3 -> NULL
         |
         4 -> 5 -> NULL
         p    r

第二次循环后：
slow -> 2 -> 4 -> 3 -> NULL
         |
         5 -> NULL
         p

最终结果：
slow -> 2 -> 5 -> 4 -> 3 -> NULL

3. 交替插入过程图解

假设： - 前半部分：L -> 1 -> 2 -> NULL - 后半部分：5 -> 4 -> 3 -> NULL（已逆置）

初始状态：
L -> 1 -> 2 -> NULL
beg = 1

5 -> 4 -> 3 -> NULL  
mid = 5

第一次插入：
L -> 1 -> 5 -> 2 -> NULL
     beg      |
              4 -> 3 -> NULL
              mid

第二次插入：
L -> 1 -> 5 -> 2 -> 4 -> NULL
          beg      |
                   3 -> NULL
                   mid

最终结果：
L -> 1 -> 5 -> 2 -> 4 -> 3 -> NULL

---

完整示例演示

假设原链表：L -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL

步骤1：找中点

slow 指向节点 3
fast 到达末尾

步骤2：断开链表

前半部分：L -> 1 -> 2 -> 3 -> NULL
后半部分：4 -> 5 -> NULL

步骤3：逆置后半部分

前半部分：L -> 1 -> 2 -> 3 -> NULL
后半部分：5 -> 4 -> NULL

步骤4：交替插入

最终结果：L -> 1 -> 5 -> 2 -> 4 -> 3 -> NULL

---

延伸知识点

1. 相关链表操作技巧

// 递归版本的链表逆置
LinkList reverseRecursive(LinkList head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    LinkList newHead = reverseRecursive(head->next);
    head->next->next = head;
    head->next = NULL;
    return newHead;
}

// 判断链表是否有环（快慢指针应用）
bool hasCycle(LinkList head) {
    LinkList slow = head, fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

2. 其他链表重排问题

// 将链表重排为 L0->Ln->L1->Ln-1->L2->Ln-2->...
// 与本题相同，这是标准解法

// 将链表按奇偶位置重排
void oddEvenList(LinkList head) {
    if (!head) return;

    LinkList odd = head, even = head->next, evenHead = even;

    while (even != NULL && even->next != NULL) {
        odd->next = even->next;
        odd = odd->next;
        even->next = odd->next;
        even = even->next;
    }

    odd->next = evenHead;
}

3. 数组版本的重排

// 数组版本的重排算法
void reorderArray(int arr[], int n) {
    int result[n];
    int left = 0, right = n - 1;
    int index = 0;

    while (left <= right) {
        if (index % 2 == 0) {
            result[index++] = arr[left++];
        } else {
            result[index++] = arr[right--];
        }
    }

    // 复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = result[i];
    }
}

4. 实际应用场景

• 数据可视化：在某些图形显示中需要特殊的节点排列方式
• 缓存策略：LRU缓存的双向链表操作
• 游戏开发：游戏对象的特殊排列需求
• 算法竞赛：经典的链表操作题目

这种方法巧妙地结合了多个链表操作技巧，包括快慢指针、链表逆置和链表合并，是链表算法中的经典题目，体现了分治思想和指针操作技巧的完美结合。