AC205-将一个带头结点的单链表 A 分解成两个带头结点的单链表 A 和 B，使 A 中包含原链表中奇数位置的元素，B 中包含偶数位置的元素，且各元素在新链表中的相对顺序保持不变¶

代码实现¶

C
// 函数 split：将带头结点的单链表 A 分解为两个链表
// A 包含奇数位置的元素，B 包含偶数位置的元素
// 位置从 1 开始计数，保持元素相对位置不变
LinkList split(LinkList A) {
    // 创建链表 B 的头结点
    LinkList B = (LinkList)malloc(sizeof(LNode));
    LinkList rb = B;        // rb 指向 B 链表的尾结点，用于尾插法
    LinkList p = A;         // p 指向 A 链表的头结点
    int pos = 1;            // 记录当前处理节点的位置（从 1 开始）

    // 遍历链表 A，处理每个节点
    while (p->next != NULL) {
        // 如果是奇数位置（第 1, 3, 5... 个节点）
        if (pos % 2 == 1) {
            p = p->next;    // 保留在 A 链表中，移动指针
        } else {
            // 如果是偶数位置（第 2, 4, 6... 个节点）
            LinkList r = p->next;       // r 指向要移动到 B 链表的节点
            p->next = r->next;          // 从 A 链表中删除该节点
            rb->next = r;               // 将该节点添加到 B 链表尾部
            rb = r;                     // 更新 B 链表的尾指针
        }
        pos++;  // 位置计数器加 1
    }

    rb->next = NULL;    // 设置 B 链表的尾结点指针为 NULL
    return B;           // 返回 B 链表的头结点
}

代码逻辑解析¶

初始化操作：
创建新链表 B 的头结点，用于存储偶数位置的元素
rb 指针用于维护 B 链表的尾部，实现尾插法
p 指针从 A 链表的头结点开始遍历
pos 变量记录当前位置（从 1 开始）
节点分类策略：
奇数位置节点（pos % 2 == 1）：保留在原链表 A 中
偶数位置节点（pos % 2 == 0）：移动到新链表 B 中
节点移动过程：
使用 r 指针指向要移动的节点
修改 p->next 跳过该节点（从 A 链表删除）
将该节点连接到 B 链表尾部
更新 B 链表的尾指针
位置计数：
每处理一个节点，位置计数器 pos 增加 1
保证了按原始位置正确分类
链表终止：
设置 B 链表尾结点的 next 指针为 NULL
返回 B 链表的头结点

修正说明¶

原代码存在一个小的逻辑错误，修正后的完整代码如下：

C
LinkList split(LinkList A) {
    LinkList B = (LinkList)malloc(sizeof(LNode));
    LinkList rb = B, p = A;
    int pos = 1;

    while (p->next != NULL) {
        if (pos % 2 == 1) {
            p = p->next;    // 奇数位置，保留在 A 中
        } else {
            LinkList r = p->next;       // 偶数位置，移动到 B 中
            p->next = r->next;          // 从 A 中删除
            rb->next = r;               // 添加到 B 尾部
            rb = r;                     // 更新 B 的尾指针
        }
        pos++;  // 位置计数器应在每次循环后递增
    }

    rb->next = NULL;    // 设置 B 链表尾部
    return B;
}

时间复杂度分析¶

链表遍历：需要遍历原链表 A 的所有节点，假设链表长度为 n，则为 O(n)
节点操作：每次节点的删除和插入操作都是 O(1) 时间复杂度
位置计算：每次的位置判断和递增都是 O(1) 操作

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

空间复杂度分析¶

新链表 B：虽然创建了新链表，但是复用了原链表中的节点，没有创建新的数据节点
辅助变量：只使用了常量级别的额外空间（如指针变量 rb, p, r 和整型变量 pos）
头结点：只为 B 链表创建了一个头结点

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

较难理解部分的说明¶

为什么使用尾插法？¶

尾插法保证了元素在新链表中的相对位置与原链表中的一致： - 按顺序处理原链表节点 - 按相同顺序插入到新链表尾部 - 避免了元素顺序的颠倒

图解说明¶

假设原链表 A 如下（位置从 1 开始）：

Text Only
1 2 3	`A: L -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL ↑ ↑ ↑ ↑ ↑ ↑ 位置: 1 2 3 4 5`

处理过程：

初始状态：

Text Only
1 2 3	`A: L -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL B: L -> NULL p -> A头结点, rb -> B头结点, pos = 1`

处理位置 1（节点 1）： - pos = 1（奇数），保留在 A 中 - p 移动到节点 1

处理位置 2（节点 2）： - pos = 2（偶数），移动到 B 中

Text Only
1 2	`A: L -> 1 -> 3 -> 4 -> 5 -> NULL B: L -> 2 -> NULL`

处理位置 3（节点 3）： - pos = 3（奇数），保留在 A 中 - p 移动到节点 3

处理位置 4（节点 4）： - pos = 4（偶数），移动到 B 中

Text Only
1 2	`A: L -> 1 -> 3 -> 5 -> NULL B: L -> 2 -> 4 -> NULL`

处理位置 5（节点 5）： - pos = 5（奇数），保留在 A 中 - p 移动到节点 5

最终结果：

Text Only
1 2	`A: L -> 1 -> 3 -> 5 -> NULL (奇数位置元素) B: L -> 2 -> 4 -> NULL (偶数位置元素)`

延伸知识点¶

1. 相关链表操作技巧¶

头插法 vs 尾插法：

C
// 头插法（会改变相对顺序）
void headInsert(LinkList head, LinkList node) {
    node->next = head->next;
    head->next = node;
}

// 尾插法（保持相对顺序）
void tailInsert(LinkList *tail, LinkList node) {
    (*tail)->next = node;
    *tail = node;
    node->next = NULL;
}

2. 类似问题变体¶

按值分类：

C
// 将链表分为正数和负数两部分
LinkList splitByValue(LinkList A) {
    LinkList B = (LinkList)malloc(sizeof(LNode));
    LinkList rb = B, p = A;

    while (p->next != NULL) {
        if (p->next->data >= 0) {
            p = p->next;  // 正数保留在 A 中
        } else {
            // 负数移动到 B 中
            LinkList r = p->next;
            p->next = r->next;
            rb->next = r;
            rb = r;
        }
    }
    rb->next = NULL;
    return B;
}

3. 扩展应用场景¶

多路分解：

C
// 将链表按位置分为三部分：1,4,7...  2,5,8...  3,6,9...
void splitToThree(LinkList A, LinkList B, LinkList C) {
    // 类似逻辑，按 pos % 3 分类
}

循环链表处理： - 需要特殊处理循环终止条件 - 注意避免无限循环

这种方法体现了链表操作中的经典技巧：原地重排和尾插法，在不创建新节点的前提下高效地重新组织数据结构。