AC204-将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中保留值大于等于0的结点，B中保留值小于0的结点¶

代码实现¶

C
// 函数 split：将带头结点的单链表 A 分解为两个链表
// A 保留值大于等于 0 的节点，B 包含值小于 0 的节点
LinkList split(LinkList A) {
    // 创建链表 B 的头节点
    LinkList B = (LinkList)malloc(sizeof(LNode));

    LinkList p = A;     // p 指针用于遍历链表 A
    LinkList rb = B;    // rb 指针指向链表 B 的尾节点，用于构建链表 B

    // 遍历链表 A，检查每个节点的后继节点
    while (p->next != NULL) {
        // 如果后继节点的值大于等于 0，保留在链表 A 中
        if (p->next->data >= 0) {
            p = p->next; // 移动 p 指针到下一个节点
        } else {
            // 如果后继节点的值小于 0，需要移动到链表 B 中
            LinkList r = p->next;        // r 指向要移动的节点
            p->next = r->next;           // 从链表 A 中删除该节点
            rb->next = r;                // 将该节点添加到链表 B 的末尾
            rb = r;                      // 更新链表 B 的尾指针
            // 注意：此时 p 指针不移动，因为还要检查新连接的节点
        }
    }

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

代码逻辑解析¶

初始化新链表：
创建链表 B 的头节点，用于存储值小于 0 的节点。
p 指针从链表 A 的头节点开始遍历。
rb 指针指向链表 B 的尾节点，用于构建链表 B。
遍历策略：
使用 p 指针遍历链表 A，但每次检查的是 p->next 节点。
这种策略便于节点的删除和移动操作。
节点分类处理：
保留节点：如果 p->next->data >= 0，节点保留在链表 A 中，p 指针向前移动。
移动节点：如果 p->next->data < 0，节点需要移动到链表 B 中。
节点移动操作：
从链表 A 中删除节点：p->next = r->next
将节点添加到链表 B 末尾：rb->next = r，然后更新尾指针 rb = r
指针移动策略：
保留节点时，p 指针正常移动。
移动节点时，p 指针不移动，因为需要继续检查新连接的节点。

时间复杂度分析¶

链表遍历：需要遍历链表 A 中的每个节点一次，时间复杂度为 O(n)
节点操作：每次节点的删除和添加操作都是 O(1) 时间复杂度
总体时间复杂度：O(n)

空间复杂度分析¶

新链表头节点：只创建了一个链表 B 的头节点，空间复杂度为 O(1)
指针变量：只使用了常量级别的额外指针变量
总体空间复杂度：O(1)

较难理解部分的说明¶

为什么使用 `p->next` 而不是直接用 `p` 遍历？¶

这种遍历方式的优势在于删除操作更加方便： - 当需要移动节点时，可以通过 p 直接修改其 next 指针来跳过被移动节点 - 避免了处理前驱节点指针的复杂性

图解说明¶

假设链表 A 为：A -> 3 -> -1 -> 2 -> -4 -> 5 -> NULL

Text Only

初始状态：
链表 A: A -> 3 -> -1 -> 2 -> -4 -> 5 -> NULL
链表 B: B -> NULL
指针: p -> A, rb -> B

步骤1: 处理节点 3 (3 >= 0)
- 保留在链表 A 中
- 移动 p 指针到节点 3
链表 A: A -> 3 -> -1 -> 2 -> -4 -> 5 -> NULL

步骤2: 处理节点 -1 (-1 < 0)  
- 从链表 A 中删除，移动到链表 B
- p 指针不移动
链表 A: A -> 3 -> 2 -> -4 -> 5 -> NULL
链表 B: B -> -1 -> NULL

步骤3: 处理节点 2 (2 >= 0)
- 保留在链表 A 中
- 移动 p 指针到节点 2
链表 A: A -> 3 -> 2 -> -4 -> 5 -> NULL

步骤4: 处理节点 -4 (-4 < 0)
- 从链表 A 中删除，移动到链表 B
- p 指针不移动
链表 A: A -> 3 -> 2 -> 5 -> NULL
链表 B: B -> -1 -> -4 -> NULL

步骤5: 处理节点 5 (5 >= 0)
- 保留在链表 A 中
- 移动 p 指针到节点 5
链表 A: A -> 3 -> 2 -> 5 -> NULL

最终结果：
链表 A: A -> 3 -> 2 -> 5 -> NULL (非负数)
链表 B: B -> -1 -> -4 -> NULL (负数)

延伸知识点¶

1. 稳定性分析¶

该算法是稳定的，即保持了相同类型节点的相对顺序： - 链表 A 中非负数的相对顺序保持不变 - 链表 B 中负数的相对顺序保持不变

2. 变体问题¶

按奇偶性分离：

C
LinkList splitEvenOdd(LinkList A) {
    LinkList B = (LinkList)malloc(sizeof(LNode));
    LinkList p = A, rb = B;

    while (p->next != NULL) {
        if (p->next->data % 2 == 0) {
            p = p->next; // 偶数保留在 A 中
        } else {
            LinkList r = p->next;
            p->next = r->next;
            rb->next = r;
            rb = r;
        }
    }
    rb->next = NULL;
    return B;
}

按指定值分离：

C
LinkList splitByValue(LinkList A, int pivot) {
    LinkList B = (LinkList)malloc(sizeof(LNode));
    LinkList p = A, rb = B;

    while (p->next != NULL) {
        if (p->next->data >= pivot) {
            p = p->next; // 大于等于 pivot 保留在 A 中
        } else {
            LinkList r = p->next;
            p->next = r->next;
            rb->next = r;
            rb = r;
        }
    }
    rb->next = NULL;
    return B;
}

3. 相关算法思想¶

双指针法： - 一个指针用于遍历原链表 - 一个指针用于构建新链表

原地操作： - 不需要额外的存储空间（除了新链表的头节点） - 直接修改原链表的指针连接关系

应用场景： - 数据分类处理 - 链表的分区操作 - 快速排序中的分区步骤

这种方法体现了链表操作中经典的节点重链接思想，通过巧妙的指针操作实现了高效的链表分解，是链表算法中的重要技巧。