AC216-将两个递增有序的循环单链表 B 合并到 A 中，保持非递减的循环单链表
代码实现
| C |
|---|
| // 函数 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 链表的第一个数据节点
B->next = NULL; // 断开 B 链表的循环结构，便于遍历
// 合并两个有序链表的核心循环
while (p != A && q != B) { // 当两个链表都未遍历完时继续
if (p->data <= q->data) {
// A 中当前元素较小或相等，将其加入合并结果
ra->next = p; // 将 p 节点连接到合并链表尾部
ra = p; // 更新尾节点指针
p = p->next; // 移动 p 指针到下一个节点
} else {
// B 中当前元素较小，将其加入合并结果
ra->next = q; // 将 q 节点连接到合并链表尾部
ra = q; // 更新尾节点指针
q = q->next; // 移动 q 指针到下一个节点
}
}
// 处理剩余节点
if (p != A) {
// A 链表还有剩余节点，直接连接到合并结果尾部
ra->next = p;
}
if (q != B) {
// B 链表还有剩余节点
ra->next = q; // 将 B 的剩余部分连接到合并结果尾部
// 找到 B 剩余部分的最后一个节点
while (q->next != B) {
q = q->next;
}
}
// 重新建立循环结构：将尾节点连接回 A 头节点
q->next = A;
}
|
代码逻辑解析
1. 循环单链表的特点
- 循环单链表的最后一个节点的
next 指针指向头节点
- 遍历终止条件是
p != 头节点 而不是 p != NULL
- 需要特殊处理循环结构的维护
2. 合并策略
采用经典的归并排序合并思想：
- 使用两个指针分别遍历两个有序链表
- 每次选择较小的元素加入结果链表
- 保持结果链表的有序性
3. 指针初始化
ra：结果链表的尾节点指针，用于构建新链表p：指向 A 链表的第一个数据节点q：指向 B 链表的第一个数据节点B->next = NULL：断开 B 的循环结构，便于标准遍历
4. 核心合并循环
通过三路比较实现有序合并：
- p->data <= q->data：选择 A 中元素
- p->data > q->data：选择 B 中元素
- 每次选择后更新尾节点指针和相应的遍历指针
5. 剩余节点处理
- 如果 A 有剩余：直接连接剩余部分
- 如果 B 有剩余：连接剩余部分并找到其尾节点
6. 循环结构重建
- 将合并后链表的尾节点重新指向 A 头节点，恢复循环结构
时间复杂度分析
- 循环次数：每次循环处理一个节点
- 节点处理：总共处理 m+n 个节点（m 为 A 的长度，n 为 B 的长度）
- 指针操作：每次操作都是 O(1)
因此，时间复杂度为 O(m + n)
空间复杂度分析
- 额外空间：只使用了常量级别的额外指针变量（ra, p, q）
- 原地操作：直接使用原有的节点空间，没有创建新节点
因此，空间复杂度为 O(1)
较难理解部分的说明
为什么需要 B->next = NULL？
循环单链表的遍历终止条件是遇到头节点。如果不断开 B 的循环结构：
| C |
|---|
| // 原始循环结构
B -> 节点1 -> 节点2 -> ... -> 节点n -> B
// 遍历时无法正常终止
while (q != B) { // 这个条件永远无法满足！
q = q->next; // q 会一直循环下去
}
|
断开后可以正常遍历：
| C |
|---|
| // 断开后的结构
B 节点1 -> 节点2 -> ... -> 节点n -> NULL
^
q
|
为什么最后需要重新找尾节点？
当 B 有剩余节点时，合并后的结构是：
| Text Only |
|---|
| A -> ... -> ra -> q(剩余B的第一个节点) -> ... -> 原B尾节点 -> ?
|
需要找到原 B 的尾节点，将其 next 指向 A，重建循环结构。
图解说明
假设：
- A 链表：A -> 1 -> 3 -> 7 -> A（循环）
- B 链表：B -> 2 -> 5 -> 8 -> B（循环）
| Text Only |
|---|
| 初始状态：
A: A -> 1 -> 3 -> 7 -> A
B: B -> 2 -> 5 -> 8 -> B
步骤1: 断开 B 循环
A: A -> 1 -> 3 -> 7 -> A
B: B 2 -> 5 -> 8 -> NULL
步骤2: 开始合并
比较 1 和 2：选择 1
结果: A -> 1
比较 3 和 2：选择 2
结果: A -> 1 -> 2
比较 3 和 5：选择 3
结果: A -> 1 -> 2 -> 3
比较 7 和 5：选择 5
结果: A -> 1 -> 2 -> 3 -> 5
比较 7 和 8：选择 7
结果: A -> 1 -> 2 -> 3 -> 5 -> 7
步骤3: A 遍历完，B 剩余 8
连接剩余部分: A -> 1 -> 2 -> 3 -> 5 -> 7 -> 8
步骤4: 重建循环
找到尾节点 8，连接回 A
最终: A -> 1 -> 2 -> 3 -> 5 -> 7 -> 8 -> A
|
延伸知识点
1. 循环链表的其他操作
| C |
|---|
| // 判断是否为循环链表
bool isCircular(LinkList head) {
if (head == NULL) return false;
LinkList slow = head, fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
// 计算循环链表长度
int getCircularLength(LinkList head) {
if (head == NULL) return 0;
LinkList p = head->next;
int count = 1;
while (p != head) {
count++;
p = p->next;
}
return count;
}
|
2. 双向循环链表的合并
| C |
|---|
| // 双向循环链表节点定义
typedef struct DNode {
int data;
struct DNode *prior, *next;
} DNode, *DLinkList;
// 双向循环链表合并需要同时维护前驱和后继指针
|
3. 错误处理版本
| C |
|---|
| // 带错误处理的合并函数
int mergeWithCheck(LinkList A, LinkList B) {
if (A == NULL || B == NULL) return -1; // 参数错误
if (A->next == A) return 0; // A 为空循环链表
if (B->next == B) return 0; // B 为空循环链表
// 正常合并逻辑...
return 1; // 合并成功
}
|
4. 实际应用场景
- 时间调度：合并两个有序的时间事件队列
- 内存管理：合并两个有序的空闲内存块链表
- 任务队列：合并两个优先级队列
- 数据库索引：合并两个有序的索引链表
这种方法体现了分治思想在链表操作中的应用，通过充分利用数据的有序性，实现了高效的合并操作，是链表算法中的经典问题。