AC208-将两个递增有序的单链表 B 合并到 A 中，形成一个非递增有序的链表¶

代码实现¶

C
// 函数 merge：将两个递增有序的单链表 B 合并到 A 中，形成一个非递增（递减）有序的链表
void merge(LinkList A, LinkList B) {
    // p 指向链表 A 的第一个数据节点，q 指向链表 B 的第一个数据节点
    LinkList p = A->next, q = B->next, r;

    // 将 A 和 B 的头节点的 next 指针置空，准备重新构建链表
    A->next = NULL;
    B->next = NULL;

    // 同时遍历两个链表，比较节点数据大小
    while (p != NULL && q != NULL) {
        // 选择较小的节点插入到结果链表的前端（头插法）
        if (p->data <= q->data) {
            r = p;        // 选择 p 节点
            p = p->next;  // 移动 p 指针到下一个节点
        } else {
            r = q;        // 选择 q 节点
            q = q->next;  // 移动 q 指针到下一个节点
        }
        // 头插法：将选中的节点插入到结果链表的前端
        r->next = A->next;
        A->next = r;
    }

    // 处理链表 A 中剩余的节点
    while (p != NULL) {
        r = p;           // 选择剩余的 p 节点
        p = p->next;     // 移动 p 指针
        r->next = A->next; // 头插法插入
        A->next = r;
    }

    // 处理链表 B 中剩余的节点
    while (q != NULL) {
        r = q;           // 选择剩余的 q 节点
        q = q->next;     // 移动 q 指针
        r->next = A->next; // 头插法插入
        A->next = r;
    }
}

代码逻辑解析¶

初始化指针：
p 指向链表 A 的第一个数据节点（跳过头节点）
q 指向链表 B 的第一个数据节点（跳过头节点）
r 用于临时存储当前要处理的节点
清空头节点：
将 A 和 B 的头节点的 next 指针置空，为重新构建链表做准备
合并过程：
使用头插法将节点逐个插入到链表 A 中
每次比较 p 和 q 指向节点的数据，选择较小的节点插入
由于是头插法，较小的元素会插入到链表前端，最终形成递减序列
处理剩余节点：
当其中一个链表遍历完后，将另一个链表的剩余节点全部插入

时间复杂度分析¶

节点遍历：
需要遍历链表 A 的所有节点（最多 m 个）
需要遍历链表 B 的所有节点（最多 n 个）
每个节点只被访问一次
操作复杂度：
每次操作（比较、指针移动、插入）都是常数时间

因此，时间复杂度为 O(m + n)，其中 m 和 n 分别是链表 A 和 B 的长度。

空间复杂度分析¶

额外空间使用：
只使用了常量级别的额外指针变量（p, q, r）
没有使用与输入规模相关的额外存储空间

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

较难理解部分的说明¶

为什么使用头插法能形成非递增序列？¶

关键在于贪心策略：每次都选择当前两个链表中较小的元素插入到结果链表的前端。

图解说明：

假设： - 链表 A：1 -> 4 -> 7 - 链表 B：2 -> 5 -> 8

合并过程：

Text Only

初始状态：
A: 头节点 -> NULL
B: 头节点 -> NULL
p: 1 -> 4 -> 7
q: 2 -> 5 -> 8

步骤1: 比较 1 和 2，选择 1
A: 头节点 -> 1 -> NULL
p: 4 -> 7
q: 2 -> 5 -> 8

步骤2: 比较 4 和 2，选择 2
A: 头节点 -> 2 -> 1 -> NULL
p: 4 -> 7
q: 5 -> 8

步骤3: 比较 4 和 5，选择 4
A: 头节点 -> 4 -> 2 -> 1 -> NULL
p: 7
q: 5 -> 8

步骤4: 比较 7 和 5，选择 5
A: 头节点 -> 5 -> 4 -> 2 -> 1 -> NULL
p: 7
q: 8

步骤5: 比较 7 和 8，选择 7
A: 头节点 -> 7 -> 5 -> 4 -> 2 -> 1 -> NULL
p: NULL
q: 8

步骤6: 处理剩余节点 8
A: 头节点 -> 8 -> 7 -> 5 -> 4 -> 2 -> 1 -> NULL

最终结果：8 -> 7 -> 5 -> 4 -> 2 -> 1（非递增序列）

延伸知识点¶

1. 头插法与尾插法的区别¶

头插法（本题使用）：

C
r->next = A->next;
A->next = r;

- 优点：实现简单，不需要额外的尾指针 - 结果：逆序排列

尾插法：

C
tail->next = r;
tail = r;
tail->next = NULL;

- 优点：保持原有顺序 - 缺点：需要维护尾指针

2. 相关变体问题¶

变体1：合并为递增序列

C
1 2	`// 如果要求递增序列，可以先用头插法得到递减序列，再反转链表 // 或者使用尾插法直接构建递增序列`

变体2：原地合并（不使用额外节点）

C
void mergeAscending(LinkList A, LinkList B) {
    LinkList pa = A, pb = B->next; // pa 是前驱指针
    while (pb != NULL) {
        LinkList temp = pb;
        pb = pb->next;
        // 找到合适的插入位置
        while (pa->next != NULL && pa->next->data < temp->data) {
            pa = pa->next;
        }
        temp->next = pa->next;
        pa->next = temp;
        pa = A; // 重置前驱指针
    }
}

3. 算法优化¶

优化版本（减少重复代码）：

C
void mergeOptimized(LinkList A, LinkList B) {
    LinkList p = A->next, q = B->next, r;
    A->next = NULL;
    B->next = NULL;

    // 主合并循环
    while (p != NULL || q != NULL) {
        if (q == NULL || (p != NULL && p->data <= q->data)) {
            r = p;
            p = p->next;
        } else {
            r = q;
            q = q->next;
        }
        r->next = A->next;
        A->next = r;
    }
}

4. 实际应用场景¶

归并排序：链表归并排序中的合并步骤
数据库合并：合并两个已排序的数据集
文件处理：合并两个已排序的文件记录

这种方法体现了分治思想在链表操作中的应用，通过简单的比较和插入操作实现了高效的有序合并。