作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区作者专栏每日更新：
LeetCode解锁1000题: 打怪升级之旅
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
引言
在算法面试中，链表问题是非常常见且基础的题型之一。题目“合并两个有序链表”要求将两个升序链表合并为一个新的升序链表并返回。这个问题考察了对链表数据结构的理解和操作能力，同时也是动态规划、递归思想的应用实例。
题目描述
给你两个升序排列的整数链表list1和list2，请你将两个链表合并，返回一个新的升序链表。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
输入：list1 = [1,2,4], list2 = [1,3,4] 输出：[1,1,2,3,4,4]
说明：
- 两个链表的节点数目范围是 [0, 50]。
- -100 <= Node.val <= 100
- list1 和 list2 均按 非递减顺序 排列
解题思路
方法一：迭代
迭代方法通过直观地比较两个链表的头节点，每次选取较小的节点添加到新链表的末尾，并移动指针，直至其中一个链表为空，最后将非空链表直接连接到新链表末尾。
代码示例
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode: dummy = ListNode(-1) prev = dummy while list1 and list2: if list1.val <= list2.val: prev.next = list1 list1 = list1.next else: prev.next = list2 list2 = list2.next prev = prev.next prev.next = list1 if list1 else list2 return dummy.next
迭代法图解
使用指针prev遍历两个链表，每次选择较小的节点连接到prev，并移动指针，直至其中一个链表为空，然后将非空链表的剩余部分连接到合并链表的末尾。
初始化
- dummy = Node(-1)作为新链表的哑节点。
- prev = dummy作为当前节点的前一个节点。
迭代过程
- 比较list1和list2的头节点[1]和[2]，将1连接到prev，移动list1。
- 比较[3]和[2]，将2连接到prev，移动list2。
- 比较[3]和[4]，将3连接到prev，移动list1。
- 比较[5]和[4]，将4连接到prev，移动list2。
- 比较[5]和[6]，将5连接到prev，移动list1。
- list1为空，将list2的剩余部分[6]连接到prev。
结果
通过迭代，最终得到的合并后的链表为[1, 2, 3, 4, 5, 6]。
方法二：递归
递归方法利用递归函数将问题分解为更小的子问题。如果list1的首元素小，那么它就应该是合并链表的首元素，其余元素由list1.next和list2合并得到；反之亦然。
代码示例
def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode: if not list1: return list2 elif not list2: return list1 elif list1.val < list2.val: list1.next = mergeTwoLists(list1.next, list2) return list1 else: list2.next = mergeTwoLists(list1, list2.next) return list2
递归算法图解
初始状态
- list1 = [1, 3, 5]
- list2 = [2, 4, 6]
我们要合并这两个列表。
递归过程
递归地比较list1和list2的头节点，选择较小的一个作为新链表的头节点，并对剩余的节点进行递归合并。
- 比较1和2，选择1，递归合并[3, 5]和[2, 4, 6]。
- 比较3和2，选择2，递归合并[3, 5]和[4, 6]。
- 比较3和4，选择3，递归合并[5]和[4, 6]。
- 比较5和4，选择4，递归合并[5]和[6]。
- 比较5和6，选择5，递归合并[]和[6]。
- list1为空，直接添加剩余的list2。
结果
合并后的链表为[1, 2, 3, 4, 5, 6]。
算法分析
时间复杂度：
- 迭代法：O(n + m)，其中n和m分别是两个链表的长度。
- 递归法：O(n + m)，递归的深度等于新链表的长度。
空间复杂度：
- 迭代法：O(1)，只使用了常数级别的额外空间。
- 递归法：O(n + m)，递归调用栈的空间。
结论
合并两个有序链表是一个基础且实用的算法问题，既可以用迭代法解决，也可以用递归法解决。这两种方法各有优缺点，迭代法更节省空间，而递归法代码更简洁。掌握这两种方法对于理解链表操作和递归思想非常有帮助。
欢迎关注微信公众号 数据分析螺丝钉
