合并两个有序链表的算法及实现

# 合并两个有序链表的算法及实现

在软件开发中，合并两个有序链表是一种常见的操作。给定两个有序链表，我们需要将它们合并成一个新的有序链表。本文将介绍合并两个有序链表的算法原理，并给出相应的代码实现。

## 1. 问题描述
假设我们有两个有序链表，分别为链表A和链表B。我们需要编写一个算法来将链表A和链表B合并成一个新的有序链表C。

例如：
链表A：1 -> 3 -> 5
链表B：2 -> 4 -> 6
合并后的链表C：1 -> 2 -> 3 -> 4 -> 5 -> 6

## 2. 算法原理
合并两个有序链表可以通过比较链表节点的值来实现。我们可以定义一个新的链表C，然后依次比较链表A和链表B中的节点，将较小的节点添加到链表C中。

具体的操作步骤如下：
- 创建一个新的链表C，并定义一个指针指向链表C的头部。
- 比较链表A的第一个节点和链表B的第一个节点的值，将较小的节点添加到链表C中。
- 指针向后移动一步。
- 重复上述步骤，直到链表A或链表B的节点为空。
- 将剩余的节点添加到链表C的末尾。

以下是使用递归方法实现合并两个有序链表的代码示例（Java）：
```java
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}
```

在上述代码中，我们首先检查链表A和链表B是否为空。如果其中一个链表为空，我们直接返回另一个链表。然后，我们比较链表A的第一个节点和链表B的第一个节点的值，将较小的节点作为合并链表的头结点。之后，我们递归地调用函数，传入剩余的链表节点进行合并，直至其中一个链表为空。最后，我们将剩余的节点添加到合并链表的末尾，并返回结果。

## 3. 时间复杂度和空间复杂度分析
合并两个有序链表的时间复杂度为O(m+n)，其中m和n分别为两个链表的长度。我们需要比较每个节点的值，并将较小的节点添加到合并链表中。

空间复杂度为O(m+n)，递归调用会占用一定的栈空间，随着链表长度的增加，递归次数也会增加。

## 4. 总结
本文介绍了合并两个有序链表的算法原理，并给出了递归方法的代码实现。合并两个有序链表可以通过比较节点的值，将较小的节点依次添加到新链表中来实现。该算法的时间复杂度为O(m+n)，空间复杂度为O(m+n)。

在实际开发中，我们可以根据具体的业务需求选择合适的解决方案。合并两个有序链表是一个常见的操作，掌握该算法可以提高代码的效率和可读性。