合并两个有序链表

合并两个有序链表可以使用递归或迭代两种方法实现。

方法一：递归

1. 如果其中一个链表为空，则返回另一个链表。
2. 如果两个链表都不为空，则比较两个链表的头结点的值，将较小的头结点作为合并后链表的头结点。
3. 将较小头结点的下一个结点设置为递归调用合并函数的结果，传入较小头结点的下一个结点和较大头结点作为参数。
4. 返回合并后的链表。

方法二：迭代

1. 创建一个新的链表作为合并后链表的头结点，同时创建一个指针用于遍历合并后链表。
2. 遍历两个链表，比较两个链表的头结点的值，将较小的头结点添加到合并后链表中，并将指针指向新的结点。
3. 将较小头结点的下一个结点作为新的较小头结点，继续比较两个链表的头结点的值。
4. 将较大头结点添加到合并后链表中，并将指针指向新的结点。
5. 将较大头结点的下一个结点作为新的较大头结点，继续比较两个链表的头结点的值。
6. 重复步骤3-5，直到其中一个链表为空。
7. 将非空链表的剩余部分添加到合并后链表的末尾。
8. 返回合并后的链表。

下面是使用Python实现的代码：

方法一：递归

def mergeTwoLists(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val < l2.val:
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    else:
        l2.next = mergeTwoLists(l1, l2.next)
        return l2

方法二：迭代

def mergeTwoLists(l1, l2):
    dummy = ListNode(0) # 创建一个虚拟头结点
    curr = dummy # 指针指向虚拟头结点
    while l1 and l2:
        if l1.val < l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2 # 将非空链表的剩余部分添加到合并后链表的末尾
    return dummy.next

以上代码中，l1和l2分别表示两个有序链表的头结点，ListNode是链表的节点类