AC206-将一个单链表 {a₁, b₁, a₂, b₂, ……, aₙ, bₙ} 拆分成两个单链表：第一个链表保持 a₁ 到 aₙ 的原始顺序，第二个链表中 b 的元素按逆序排列¶

代码实现¶

C
// 函数 split：将单链表 {a1,b1,a2,b2,...,an,bn} 拆分成两个链表
// 第一个链表保持 {a1,a2,...,an} 的顺序
// 第二个链表为 {bn,bn-1,...,b1} 的逆序
LinkList split(LinkList A) {
    // 创建新链表 B 的头节点
    LinkList B = (LinkList)malloc(sizeof(LNode));
    B->next = NULL; // 初始化链表 B 为空

    LinkList p = A; // p 指针用于遍历原链表 A
    int pos = 1;    // 位置计数器，用于判断当前节点是奇数位还是偶数位

    // 遍历原链表 A，处理每个节点
    while (p->next != NULL) {
        // 如果是奇数位置（a1, a2, ..., an），保留在此链表中
        if (pos % 2 == 1) {
            p = p->next; // 移动指针，不进行任何操作
        } else {
            // 如果是偶数位置（b1, b2, ..., bn），将其移动到链表 B
            LinkList r = p->next;      // r 指向要移动的节点
            p->next = r->next;         // 从原链表 A 中删除该节点
            r->next = B->next;         // 将该节点插入到链表 B 的头部
            B->next = r;               // 更新链表 B 的头指针
            // 注意：此时 p 指针不移动，因为要继续处理新连接的节点
        }
        pos++; // 位置计数器加1
    }

    return B; // 返回新创建的链表 B
}

代码逻辑解析¶

1. 问题理解¶

原始链表结构：{a1, b1, a2, b2, ..., an, bn}（共 2n 个节点） - 目标1：链表 A 保持 {a1, a2, ..., an} 的顺序 - 目标2：链表 B 存储 {bn, bn-1, ..., b1} 的逆序

2. 算法策略¶

使用位置计数器 pos 来区分奇数位（a系列）和偶数位（b系列）
奇数位节点保留在原链表中
偶数位节点从原链表中删除，并采用头插法插入到新链表 B 中

3. 头插法的关键作用¶

由于采用头插法插入到链表 B： - 第一个被移动的 b1 节点会成为 B 链表的最后一个节点 - 最后一个被移动的 bn 节点会成为 B 链表的第一个节点 - 从而实现了 {bn, bn-1, ..., b1} 的逆序效果

4. 指针操作详解¶

Text Only
1 2	`原链表 A: ... -> p -> r -> next_node -> ... 移动后: ... -> p -> next_node -> ... (r 被移动到 B)`

时间复杂度分析¶

链表遍历：需要遍历原链表的一次，共 2n 个节点，时间复杂度为 O(2n) = O(n)
节点操作：每次节点的删除和插入操作都是常数时间 O(1)
总操作次数：最多进行 n 次节点移动操作

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

空间复杂度分析¶

辅助空间：只创建了一个新链表的头节点 B，占用常数空间 O(1)
指针变量：使用了常量级别的额外指针变量 p, r, pos

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

较难理解部分的说明¶

为什么采用头插法能实现逆序？¶

让我们通过具体例子来说明：

假设原链表为：A -> a1 -> b1 -> a2 -> b2 -> a3 -> b3 -> NULL

处理过程： 1. pos=1：a1（奇数位）→ 保留在 A 中 2. pos=2：b1（偶数位）→ 移动到 B，B: B -> b1 -> NULL 3. pos=3：a2（奇数位）→ 保留在 A 中
4. pos=4：b2（偶数位）→ 移动到 B，B: B -> b2 -> b1 -> NULL 5. pos=5：a3（奇数位）→ 保留在 A 中 6. pos=6：b3（偶数位）→ 移动到 B，B: B -> b3 -> b2 -> b1 -> NULL

图解说明：

Text Only

初始状态：
A: A_head -> a1 -> b1 -> a2 -> b2 -> a3 -> b3 -> NULL
B: B_head -> NULL

第一次移动 b1：
A: A_head -> a1 -> a2 -> b2 -> a3 -> b3 -> NULL
B: B_head -> b1 -> NULL

第二次移动 b2：
A: A_head -> a1 -> a2 -> a3 -> b3 -> NULL  
B: B_head -> b2 -> b1 -> NULL

第三次移动 b3：
A: A_head -> a1 -> a2 -> a3 -> NULL
B: B_head -> b3 -> b2 -> b1 -> NULL

最终结果： - 链表 A：{a1, a2, a3} - 链表 B：{b3, b2, b1}（即 {b3, b2, b1} 的逆序）

延伸知识点¶

1. 类似问题变体¶

变体1：保持 b 系列的原始顺序

C
1 2	`// 如果要求 B 链表为 {b1, b2, ..., bn} 的原始顺序 // 可以先按逆序存储，最后再进行一次链表反转`

变体2：三等分链表

C
// 将 {a1,b1,c1,a2,b2,c2,...,an,bn,cn} 拆分为三个链表
if (pos % 3 == 1) { /* a 系列 */ }
else if (pos % 3 == 2) { /* b 系列 */ }
else { /* c 系列，采用尾插法保持顺序 */ }

2. 链表操作技巧¶

头插法 vs 尾插法： - 头插法：插入新节点到链表头部，实现逆序效果 - 尾插法：插入新节点到链表尾部，保持原有顺序

双指针技巧：

C
// 另一种实现方式：使用快慢指针
LinkList slow = A, fast = A;
while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
}
// slow 指向中间位置

3. 实际应用场景¶

数据分组处理：将交替存储的数据分离到不同的处理队列
缓存管理：将访问频率不同的数据分离存储
任务调度：将不同类型的任务分配到不同的执行队列

4. 错误处理和边界情况¶

在实际应用中还需要考虑：

C
LinkList split(LinkList A) {
    // 边界检查
    if (A == NULL || A->next == NULL) {
        return NULL;
    }

    // 内存分配检查
    LinkList B = (LinkList)malloc(sizeof(LNode));
    if (B == NULL) {
        return NULL; // 内存分配失败
    }

    // ... 原有逻辑 ...

    return B;
}

这个算法体现了链表操作中原地修改和头插法逆序的经典技巧，是链表算法中的重要知识点。