链表归并（链表归并排序空间复杂度）

链表归并是一种常见的算法，用于将两个有序链表合并为一个有序链表。在计算机科学领域，链表归并被广泛应用于排序算法和合并排序算法中。本文将介绍链表归并的基本原理和实现方法。

## 1. 链表归并的基本原理

链表归并的基本原理是通过比较两个有序链表的节点值，将较小的节点插入到新的有序链表中。具体步骤如下：

1. 创建一个新的链表和一个指针，用于指向新链表的当前节点；

2. 比较两个链表的当前节点值，将较小的节点插入到新链表中，并将指针移动到下一个节点；

3. 重复上述步骤，直到其中一个链表为空；

4. 将另一个链表剩余的节点直接插入到新链表的末尾。

## 2. 链表归并的实现方法

链表归并的实现方法可以使用递归或迭代的方式。

### 2.1 递归实现

递归实现链表归并的步骤如下：

1. 如果其中一个链表为空，直接返回另一个链表；

2. 如果两个链表的当前节点值相等，将其中一个节点插入到新链表中，并递归处理剩余节点；

3. 如果链表1的当前节点值小于链表2的当前节点值，将链表1的当前节点插入到新链表中，并递归处理链表1的下一个节点和链表2的当前节点；

4. 如果链表1的当前节点值大于链表2的当前节点值，将链表2的当前节点插入到新链表中，并递归处理链表1的当前节点和链表2的下一个节点。

### 2.2 迭代实现

迭代实现链表归并的步骤如下：

1. 创建一个新的链表和一个指针，用于指向新链表的当前节点；

2. 比较两个链表的当前节点值，将较小的节点插入到新链表中，并将指针移动到下一个节点；

3. 重复上述步骤，直到其中一个链表为空；

4. 将另一个链表剩余的节点直接插入到新链表的末尾。

## 3. 链表归并的应用

链表归并算法在排序算法和合并排序算法中起到关键作用。在排序算法中，可以使用链表归并对数组进行划分，然后递归地进行归并排序。在合并排序算法中，可以使用链表归并对多个有序链表进行合并操作。

总结起来，链表归并是一种重要的算法，用于将两个有序链表合并为一个有序链表。它可以通过递归或迭代的方式实现。链表归并在排序算法和合并排序算法中起到关键作用。我们可以利用链表归并算法解决排序和合并问题，提高算法的效率。