跳转至

AC207-将两个递增有序的单链表 B 合并到 A 中，仍保持非递减有序

代码实现

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 函数 merge：将两个递增有序的单链表 B 合并到 A 中，仍保持非递减有序
void merge(LinkList A, LinkList B) {
    LinkList ra = A; // ra 指向链表 A 的头节点，用于构建合并后的链表
    LinkList p = A->next; // p 指向链表 A 的第一个实际节点
    LinkList q = B->next; // q 指向链表 B 的第一个实际节点

    // 双指针遍历链表 A 和 B，按非递减顺序合并
    while (p != NULL && q != NULL) {
        if (p->data <= q->data) {
            // 如果 p 的数据小于等于 q 的数据，则将 p 接入合并链表
            ra->next = p;
            ra = p; // 移动 ra 到新接入的节点
            p = p->next; // 移动 p 到下一个节点
        } else {
            // 如果 q 的数据小于 p 的数据，则将 q 接入合并链表
            ra->next = q;
            ra = q; // 移动 ra 到新接入的节点
            q = q->next; // 移动 q 到下一个节点
        }
    }

    // 处理剩余部分
    if (p != NULL) {
        ra->next = p; // 如果链表 A 还有剩余节点，直接接上
    }
    if (q != NULL) {
        ra->next = q; // 如果链表 B 还有剩余节点，直接接上
    }

    // 释放链表 B 的头节点（因为 B 的头节点不再需要）
    free(B);
}

代码逻辑解析

  1. 初始化指针：
  2. ra 指向链表 A 的头节点，用于构建合并后的链表。
  3. p 指向链表 A 的第一个实际节点。

  4. q 指向链表 B 的第一个实际节点。

  5. 双指针遍历与合并：

  6. 使用 while 循环同时遍历链表 A 和 B，直到其中一个链表被完全遍历完。

  7. 在每次循环中比较 p->data 和 q->data：

    • 如果 p->data <= q->data，将 p 接入合并链表，并移动 p 和 ra；
    • 否则，将 q 接入合并链表，并移动 q 和 ra。

  8. 处理剩余节点：

  9. 如果链表 A 或链表 B 还有未处理的节点，直接将其接到合并链表的末尾。

  10. 释放链表 B 的头节点：

  11. 因为链表 B 的头节点已经没有实际用途，且其内容可能被合并到链表 A 中，因此释放其内存。

时间复杂度分析

  • 遍历链表 A 和 B：
  • 假设链表 A 的长度为 m，链表 B 的长度为 n。
  • 每次循环都会处理一个节点（来自 A 或 B），因此总的循环次数为 m + n。

  • 时间复杂度为 O(m + n)。

  • 其他操作：

  • 初始化、剩余节点处理和释放头节点的操作均为 O(1)。

综上，时间复杂度为 O(m + n)。

空间复杂度分析

  • 该算法只使用了常量级别的额外空间（如变量 ra, p, q），没有使用与输入规模相关的额外空间。
  • 因此，空间复杂度为 O(1)。

较难理解部分的说明

为什么需要 ra 指针？

  • ra 是一个辅助指针，用于记录当前合并链表的最后一个节点。
  • 它的作用是确保每次都能正确地将新的节点接入合并链表，避免断链或错误连接。

图解说明

假设链表 A 和 B 如下：

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

初始状态：

Text Only
1
2
3
ra -> A (头节点)
p -> 1
q -> 2

  • 第一次循环：p->data = 1，q->data = 2，p->data < q->data，将 p 接入合并链表。

    Text Only
    1
2
    合并链表: A -> 1 -> NULL
p -> 3

  • 第二次循环：p->data = 3，q->data = 2，p->data > q->data，将 q 接入合并链表。

    Text Only
    1
2
    合并链表: A -> 1 -> 2 -> NULL
q -> 4

  • 第三次循环：p->data = 3，q->data = 4，p->data < q->data，将 p 接入合并链表。

    Text Only
    1
2
    合并链表: A -> 1 -> 2 -> 3 -> NULL
p -> 5

  • 第四次循环：p->data = 5，q->data = 4，p->data > q->data，将 q 接入合并链表。

    Text Only
    1
2
    合并链表: A -> 1 -> 2 -> 3 -> 4 -> NULL
q -> 6

  • 第五次循环：p->data = 5，q->data = 6，p->data < q->data，将 p 接入合并链表。

    Text Only
    1
2
    合并链表: A -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
p -> NULL

  • 最后处理剩余节点：q 不为空，将 q 接入合并链表。

    Text Only
    1
    合并链表: A -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

最终结果：

Text Only
1
A: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

延伸知识点

1. 双指针法的应用

双指针法广泛应用于有序数组或链表的合并问题，例如： - 合并两个有序数组。 - 合并多个有序链表（可以扩展为优先队列）。

2. 链表头节点的作用

  • 链表的头节点通常是一个空节点，用于简化插入和删除操作。
  • 在本例中，A 的头节点充当了合并链表的起点。

3. 相关算法问题

变体问题：

  • 如果要求合并后的链表是递减有序的，如何修改算法？

    C
    1
2
3
4
5
6
7
8
9
    if (p->data >= q->data) {
    ra->next = p;
    ra = p;
    p = p->next;
} else {
    ra->next = q;
    ra = q;
    q = q->next;
}

  • 如果链表 A 和 B 中可能存在重复元素，是否需要去重？如何实现？

应用场景：

  • 数据库中的有序数据合并。
  • 文件系统的块合并操作。
  • 实时数据流的排序与合并。

通过这种双指针方法，可以在原地完成链表的合并，既高效又节省空间。