合并两个有序链表：递归和迭代两种方法实现

合并两个有序链表可以使用递归或迭代两种方法实现。\n\n方法一：递归\n1. 如果其中一个链表为空，则返回另一个链表。\n2. 如果两个链表都不为空，则比较两个链表的头结点的值，将较小的头结点作为合并后链表的头结点。\n3. 将较小头结点的下一个结点设置为递归调用合并函数的结果，传入较小头结点的下一个结点和较大头结点作为参数。\n4. 返回合并后的链表。\n\n方法二：迭代\n1. 创建一个新的链表作为合并后链表的头结点，同时创建一个指针用于遍历合并后链表。\n2. 遍历两个链表，比较两个链表的头结点的值，将较小的头结点添加到合并后链表中，并将指针指向新的结点。\n3. 将较小头结点的下一个结点作为新的较小头结点，继续比较两个链表的头结点的值。\n4. 将较大头结点添加到合并后链表中，并将指针指向新的结点。\n5. 将较大头结点的下一个结点作为新的较大头结点，继续比较两个链表的头结点的值。\n6. 重复步骤3-5，直到其中一个链表为空。\n7. 将非空链表的剩余部分添加到合并后链表的末尾。\n8. 返回合并后的链表。\n\n下面是使用Python实现的代码：\n\n方法一：递归\n\npython\ndef mergeTwoLists(l1, l2):\n if not l1:\n return l2\n if not l2:\n return l1\n if l1.val < l2.val:\n l1.next = mergeTwoLists(l1.next, l2)\n return l1\n else:\n l2.next = mergeTwoLists(l1, l2.next)\n return l2\n\n\n方法二：迭代\n\npython\ndef mergeTwoLists(l1, l2):\n dummy = ListNode(0) # 创建一个虚拟头结点\n curr = dummy # 指针指向虚拟头结点\n while l1 and l2:\n if l1.val < l2.val:\n curr.next = l1\n l1 = l1.next\n else:\n curr.next = l2\n l2 = l2.next\n curr = curr.next\n curr.next = l1 or l2 # 将非空链表的剩余部分添加到合并后链表的末尾\n return dummy.next\n\n\n以上代码中，l1和l2分别表示两个有序链表的头结点，ListNode是链表的节点类。