合并2个有序链表 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 # 返回合并后的新链表头结点 ``` 上述代码中，`dummy` 是用于构建新链表的一个辅助节点，最后返回 `dummy.next` 即可得到完整的链表[^3]。 --- #### 递归法实现递归方法的思想是每次找到两个链表头部最小的那个节点，将其作为新的链表头节点，并继续处理剩下的部分[^4]。具体实现如下： ```python def mergeTwoListsRecursive(list1: ListNode, list2: ListNode) -> ListNode: if not list1: return list2 if not list2: return list1 if list1.val < list2.val: list1.next = mergeTwoListsRecursive(list1.next, list2) return list1 else: list2.next = mergeTwoListsRecursive(list1, list2.next) return list2 ``` 该方法利用了递归特性简化逻辑结构，但在极端情况下可能会因为递归层数过深而导致栈溢出[^2]。 --- #### 时间复杂度与空间复杂度分析 - **时间复杂度**: O(n + m)，其中 n 和 m 分别代表输入两链表长度。无论采用哪种方式都需要遍历整个数据集合一次。 - **空间复杂度**: - 对于迭代版本来说，额外只需要常数级变量存储中间状态，因此其空间开销为 O(1)； - 如果选择递归，则取决于调用堆栈的最大深度，在最坏情形下可能达到 O(max(n,m)) 的级别。 --- #### 应用场景扩展除了基本功能外，“合并两个有序链表”的技术还可以应用于更复杂的领域，比如多路归并排序、大规模分布式计算环境下的文件读取操作等实际工作中常见需求之中。 ---

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

下一篇 Python写一个爬虫爬取https://www.goofish.com/这个网站关于PLC的内容