有序链表合并（有序链表合并算法c语言代码）

## 有序链表合并### 简介有序链表合并是一种将两个或多个已排序的链表合并成一个新链表的技术，从而确保新链表也按升序排列。### 合并算法#### 递归方法

算法步骤：

1. 如果其中一个链表为空，则返回另一个链表。 2. 比较两个链表中当前节点的值。 3. 将较小值节点插入新链表并更新指针。 4. 递归调用该算法，将较小值节点的下一个节点作为参数。

示例：

两个有序链表：``` [1, 3, 5] [2, 4, 6] ```递归合并过程：``` compare(1, 2) => 1 compare(3, 2) => 2 compare(3, 4) => 3 compare(5, 4) => 4 compare(5, 6) => 5 compare(6, None) => 6合并后的链表：[1, 2, 3, 4, 5, 6] ```#### 迭代方法

算法步骤：

1. 创建一个哨兵节点（dummy node）作为新链表的头部。 2. 设置两个指针分别指向两个链表的头部。 3. 循环，直到两个指针都为 None：- 比较两个指针指向节点的值。- 将较小值节点添加到新链表并更新指针。 4. 将剩余的节点添加到新链表。

示例：

``` dummy -> [None] left -> [1, 3, 5] right -> [2, 4, 6]while left & right is not None:if left.val < right.val:dummy.next = leftleft = left.nextelse:dummy.next = rightright = right.nextdummy.next = left or right合并后的链表：[1, 2, 3, 4, 5, 6] ```### 应用有序链表合并算法在以下场景中很有用：- 将多个已排序的数据集合并为一个有序数据集。 - 求两个有序链表的中位数。 - 排序大型数据集，采用分治策略。 - 实现归并排序算法。