AC217-将两个循环单链表连接，将 h2 链表接到 h1 之后

代码实现

// 函数 link：将两个循环单链表连接，将 h2 链表接到 h1 之后
// 要求：连接后仍保持循环链表形式，保留 h1 头节点，剔除 h2 头节点
void link(LinkList h1, LinkList h2) {
    LinkList p, q; // 定义两个指针用于遍历

    p = h1; // p 指向 h1 链表的头节点
    q = h2; // q 指向 h2 链表的头节点

    // 找到 h1 链表的尾节点（最后一个数据节点）
    // 循环条件：p 的 next 不指向头节点 h1
    while (p->next != h1) {
        p = p->next; // 向后移动指针
    }

    // 找到 h2 链表的尾节点（最后一个数据节点）
    // 循环条件：q 的 next 不指向头节点 h2
    while (q->next != h2) {
        q = q->next; // 向后移动指针
    }

    // 执行连接操作
    p->next = h2->next; // 将 h1 的尾节点指向 h2 的第一个数据节点（跳过 h2 头节点）
    q->next = h1;       // 将 h2 的尾节点指向 h1 的头节点，完成循环
}

---

代码逻辑解析

1. 循环链表的特点

• 循环链表中，最后一个节点的 next 指针指向头节点
• 通过判断 p->next == h1 来识别 h1 链表的尾节点
• 通过判断 q->next == h2 来识别 h2 链表的尾节点

2. 连接步骤详解

步骤1：定位 h1 的尾节点

h1 -> 节点1 -> 节点2 -> ... -> 节点m -> h1
                                     ↑
                                   尾节点p

步骤2：定位 h2 的尾节点

h2 -> 节点1 -> 节点2 -> ... -> 节点n -> h2
                                     ↑
                                   尾节点q

步骤3：执行连接操作

原状态：
h1 -> A1 -> A2 -> ... -> Am -> h1
h2 -> B1 -> B2 -> ... -> Bn -> h2

连接后：
h1 -> A1 -> A2 -> ... -> Am -> B1 -> B2 -> ... -> Bn -> h1

3. 关键设计要点

• 保留 h1 头节点：h1 作为新链表的头节点继续存在
• 剔除 h2 头节点：不将 h2 头节点包含在结果链表中
• 维持循环结构：最终结果仍然是一个完整的循环链表

---

时间复杂度分析

• 寻找 h1 尾节点：O(m) - 需要遍历 h1 链表的所有节点
• 寻找 h2 尾节点：O(n) - 需要遍历 h2 链表的所有节点
• 连接操作：O(1) - 只涉及两个指针的修改

因此，总的时间复杂度为 O(m + n) = O(max(m, n))

---

空间复杂度分析

• 额外空间使用：只使用了常量级别的额外变量（p, q）
• 无额外内存分配：没有创建新的节点或数组

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

---

较难理解部分的说明

循环链表的遍历终止条件

// 循环链表遍历的关键：用头节点作为终止标志
while (p->next != h1) {  // 当下一个节点不是头节点时继续
    p = p->next;
}

这与普通链表的 p != NULL 判断不同，循环链表永远不会遇到 NULL。

图解说明

假设： - h1 链表：h1 -> 1 -> 2 -> 3 -> h1 - h2 链表：h2 -> 4 -> 5 -> 6 -> h2

初始状态：
h1 ──→ 1 ──→ 2 ──→ 3 ──┐
 │                     │
 └─────────────────────┘

h2 ──→ 4 ──→ 5 ──→ 6 ──┐
 │                     │
 └─────────────────────┘

步骤1：找到 h1 的尾节点（节点3）
p 指向节点3

步骤2：找到 h2 的尾节点（节点6）  
q 指向节点6

步骤3：执行连接操作
p->next = h2->next;  // 节点3 -> 节点4
q->next = h1;        // 节点6 -> h1

最终结果：
h1 ──→ 1 ──→ 2 ──→ 3 ──→ 4 ──→ 5 ──→ 6 ──┐
 │                                        │
 └────────────────────────────────────────┘

---

延伸知识点

1. 循环链表的基本操作

// 创建循环链表
LinkList createCircularList() {
    LinkList head = (LinkList)malloc(sizeof(LNode));
    head->next = head; // 自循环
    return head;
}

// 判断是否为空循环链表
int isEmpty(LinkList head) {
    return head->next == head;
}

// 计算循环链表长度
int length(LinkList head) {
    if (head->next == head) return 0;
    int count = 0;
    LinkList p = head->next;
    while (p != head) {
        count++;
        p = p->next;
    }
    return count;
}

2. 安全版本 - 添加空指针检查

// 更安全的连接函数，添加错误检查
void linkSafe(LinkList h1, LinkList h2) {
    // 参数检查
    if (h1 == NULL || h2 == NULL) return;
    if (h1 == h2) return; // 避免自连接

    LinkList p = h1, q = h2;

    // 找到 h1 的尾节点
    while (p->next != h1) {
        p = p->next;
    }

    // 找到 h2 的尾节点
    while (q->next != h2) {
        q = q->next;
    }

    // 执行连接
    p->next = h2->next; // 跳过 h2 头节点
    q->next = h1;
}

3. 双向循环链表的连接

// 双向循环链表的连接（需要同时处理前驱指针）
void linkDoubleCircular(DLinkList h1, DLinkList h2) {
    DLinkList p = h1->prior;  // h1 的尾节点
    DLinkList q = h2->prior;  // h2 的尾节点

    // 连接操作
    p->next = h2->next;       // h1尾 -> h2首
    h2->next->prior = p;      // h2首的前驱 -> h1尾
    q->next = h1;             // h2尾 -> h1头
    h1->prior = q;            // h1头的前驱 -> h2尾
}

4. 相关应用场景

• 约瑟夫问题：循环链表是解决约瑟夫问题的理想数据结构
• 缓冲区管理：循环缓冲区的实现
• 游戏开发：玩家轮流操作的循环队列
• 操作系统：进程调度中的循环队列

5. 循环链表 vs 普通链表

特性	普通链表	循环链表
尾节点	next = NULL	next = 头节点
遍历终止条件	p != NULL	p != 头节点
插入删除	需要特殊处理头节点	相对统一
应用场景	一般线性结构	循环处理场景

这种方法体现了数据结构特性利用的设计思想，通过巧妙地修改指针连接，实现了两个循环链表的高效合并，保持了循环链表的结构完整性。