### 合并两个有序单链表为一个有序链表的Python实现 在Python中，合并两个有序单链表可以通过迭代或递归的方式实现。以下是详细的解析和代码实现。 #### 标准求解【直接合并】 使用迭代方法创建一个新的链表，并通过两个指针分别遍历输入的两个链表。每次比较两个指针指向节点的值，将较小的节点添加到新链表中，直到其中一个链表被完全遍历。最后，将另一个未遍历完的链表直接连接到新链表的末尾[^1]。 ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode: # 创建一个虚拟头节点 dummy = ListNode() current = dummy # 遍历两个链表 while list1 and list2: if list1.val < list2.val: current.next = list1 list1 = list1.next else: current.next = list2 list2 = list2.next current = current.next # 连接剩余部分 if list1: current.next = list1 elif list2: current.next = list2 return dummy.next ``` #### 改进版一【列表合并】 另一种思路是先将两个链表的节点值存储到一个列表中，然后对列表进行排序，最后根据排序后的列表重新构建链表[^1]。 ```python def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode: # 将两个链表的值提取到列表中 values = [] while list1: values.append(list1.val) list1 = list1.next while list2: values.append(list2.val) list2 = list2.next # 对列表进行排序 values.sort() # 构建新的链表 dummy = ListNode() current = dummy for val in values: current.next = ListNode(val) current = current.next return dummy.next ``` #### 改进版二【递归大法】 递归方法通过不断比较两个链表的当前节点值，选择较小的一个作为结果链表的当前节点，并递归地处理剩余部分[^1]。 ```python def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode: if not list1: return list2 if not list2: return list1 if list1.val < list2.val: list1.next = mergeTwoLists(list1.next, list2) return list1 else: list2.next = mergeTwoLists(list1, list2.next) return list2 ``` 以上三种方法都可以有效地合并两个有序单链表为一个有序链表，具体选择哪种方法取决于实际需求和场景。 ---