### 合并两个有序链表的 Python 实现 #### 问题概述 合并两个有序链表的任务是指将两个已经按升序排列的单向链表合并成一个新的有序链表。新链表应由原有两个链表中的所有节点组成。 #### 方法解析 以下是几种常见的方法来解决此问题： 1. **标准求解（直接合并）** 使用迭代的方式逐一比较两个链表当前节点的值，较小者被加入到新的链表中，直到其中一个链表为空为止[^1]。 2. **改进版一（列表合并）** 将两个链表转换为数组形式，在数组层面完成排序后再重新构建链表[^2]。 3. **改进版二（递归大法）** 利用递归的思想处理每一个子问题，即每次只考虑当前两链表头部哪个更小，并将其连接至最终结果上[^3]。 下面展示具体的代码实现方式及其解释： #### 标准求解【直接合并】 ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode: dummy = ListNode(0) current = dummy while l1 and l2: if l1.val < l2.val: current.next = l1 l1 = l1.next else: current.next = l2 l2 = l2.next current = current.next current.next = l1 or l2 return dummy.next ``` 这段代码定义了一个辅助类 `ListNode` 表示链表的一个结点以及核心函数 `mergeTwoLists` 来执行实际的合并操作[^4]。 #### 改进版二【递归大法】 ```python def mergeTwoListsRecursive(l1: ListNode, l2: ListNode) -> ListNode: if not l1: return l2 elif not l2: return l1 elif l1.val < l2.val: l1.next = mergeTwoListsRecursive(l1.next, l2) return l1 else: l2.next = mergeTwoListsRecursive(l1, l2.next) return l2 ``` 通过上述两种主要策略可以有效地解决问题，其中递归版本通常更加简洁明了但可能带来额外栈空间消耗；而迭代则相对稳定且易于理解控制流程。 #### 最优算法分析 对于时间复杂度而言，无论是采用迭代还是递归方案，其最佳情况均为 O(n+m)，这里 n 和 m 分别代表输入两条链表长度之和。这是因为每个元素最多只会访问一次即可决定位置关系。