剑指 Offer：合并两个有序链表 - 详解与 Python 代码实现

要合并两个单调递增的链表，可以使用递归的方法。假设两个链表分别为list1和list2。\n\n首先，判断list1和list2是否为空，如果其中一个链表为空，直接返回另一个链表。然后判断list1和list2的头节点的值，将较小的节点作为合并后的链表的头节点。然后，递归地合并剩余的节点。\n\n具体的步骤如下：\n\n1. 如果list1为空，返回list2。\n2. 如果list2为空，返回list1。\n3. 如果list1的头节点的值小于等于list2的头节点的值，将list1的头节点作为合并后的链表的头节点，然后递归地合并list1的剩余节点和list2。\n4. 如果list1的头节点的值大于list2的头节点的值，将list2的头节点作为合并后的链表的头节点，然后递归地合并list1和list2的剩余节点。\n\n代码如下：\n\npython\nclass ListNode:\n def __init__(self, x):\n self.val = x\n self.next = None\n\ndef mergeTwoLists(list1, list2):\n if not list1:\n return list2\n if not list2:\n return list1\n\n if list1.val <= list2.val:\n merged = list1\n merged.next = mergeTwoLists(list1.next, list2)\n else:\n merged = list2\n merged.next = mergeTwoLists(list1, list2.next)\n\n return merged\n\n\n时间复杂度分析：假设两个链表的长度分别为m和n，合并两个链表的过程需要遍历所有的节点，所以时间复杂度为O(m + n)。\n\n空间复杂度分析：递归的过程中需要使用系统栈空间，栈的深度为两个链表的最大长度，所以空间复杂度为O(max(m, n))。