LeetCode 21合并两个有序链表迭代递归详细解析问题描述将两个升序排列的链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的不改变原链表的节点结构仅通过调整节点的next指针实现合并。示例说明示例 1输入l1 [1,2,4], l2 [1,3,4]输出[1,1,2,3,4,4]解释两个升序链表合并后仍保持升序拼接所有节点得到新链表。示例 2输入l1 [], l2 []输出[]解释两个空链表合并后仍为空。示例 3输入l1 [], l2 [0]输出[0]解释空链表与非空有序链表合并结果为非空链表本身。提示信息两个链表的节点数目范围是 [0, 50]允许其中一个或两个链表为空。节点值范围-100 ≤ Node.val ≤ 100。l1 和 l2 均按非递减顺序升序排列合并后需保持该顺序。解题思路本题核心是利用两个链表的“升序”特性通过“逐个比较节点值”的方式将较小的节点依次拼接最终形成新的升序链表。常用两种解题方法迭代法推荐易理解、效率高和递归法代码简洁体现递归思想以下分别详解。方法一迭代法最优解核心思路创建一个虚拟头节点dummy node用于简化新链表的拼接操作无需单独处理头节点为空的情况。定义一个指针curr指向虚拟头节点用于遍历并拼接新链表。同时遍历两个输入链表list1和list2每次比较两个链表当前节点的值将值较小的节点接入新链表curr.next指向该节点。将对应链表的指针向后移动一位如list1节点值小则list1 list1.next。将curr指针向后移动一位准备拼接下一个节点。当其中一个链表遍历完毕后将另一个链表的剩余节点直接接入新链表尾部剩余节点已升序无需再比较。返回虚拟头节点的next即为合并后的新链表头节点。方法二递归法核心思路利用递归的“分治思想”将两个链表的合并问题拆解为“当前最小节点 剩余链表合并”的子问题终止条件为其中一个链表为空。终止条件若list1为空返回list2若list2为空返回list1空链表与非空链表合并结果为非空链表。递归逻辑若list1.val ≤ list2.val则当前节点选择list1且list1.next等于“list1.next与list2合并后的结果”。否则当前节点选择list2且list2.next等于“list1与list2.next合并后的结果”。递归返回每次返回当前选择的节点最终递归结束后返回的节点即为合并后链表的头节点。注意递归法代码简洁但递归深度取决于两个链表的总长度最大为100未超过Python默认递归深度1000不会出现栈溢出问题。完整代码两种方法方法一迭代法推荐时间/空间最优LeetCode 21 迭代法 AC代码# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) - Optional[ListNode]: # 虚拟头节点简化头节点拼接逻辑 dummy ListNode(val-1) # curr指针用于遍历并拼接新链表 curr dummy # 同时遍历两个链表直到其中一个遍历完毕 while list1 and list2: # 比较当前两个节点的值拼接较小的节点 if list1.val list2.val: curr.next list1 list1 list1.next # list1指针后移 else: curr.next list2 list2 list2.next # list2指针后移 curr curr.next # curr指针后移准备拼接下一个节点 # 将剩余未遍历完的链表直接接入新链表尾部 curr.next list1 if list1 else list2 # 返回合并后链表的头节点虚拟头节点的next return dummy.next方法二递归法代码简洁适合理解递归思想LeetCode 21 递归法 AC代码# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) - Optional[ListNode]: # 终止条件其中一个链表为空返回另一个链表 if not list1: return list2 if not list2: return list1 # 递归逻辑选择当前较小的节点递归合并剩余链表 if list1.val list2.val: list1.next self.mergeTwoLists(list1.next, list2) return list1 else: list2.next self.mergeTwoLists(list1, list2.next) return list2代码解析一、迭代法代码解析虚拟头节点创建dummy ListNode(val-1)其作用是统一拼接逻辑——无论两个输入链表是否为空都可以通过curr.next拼接节点无需单独判断头节点。遍历与拼接while list1 and list2循环条件确保只有两个链表都有节点时才进行比较避免空指针异常。每次比较后将较小节点接入新链表并移动对应指针。剩余节点处理循环结束后必然有一个链表已遍历完毕剩余节点本身是升序的直接通过curr.next list1 if list1 else list2接入尾部无需再逐个比较。返回结果虚拟头节点的next才是合并后链表的真实头节点返回dummy.next即可。二、递归法代码解析终止条件当list1或list2为空时直接返回另一个链表这是递归的“出口”也是处理空链表的核心逻辑。递归调用每次递归只做一件事——选择当前较小的节点然后让该节点的next指向“剩余两个链表合并的结果”本质是将大问题拆解为更小的子问题逐步递归求解。返回值每次递归返回当前选择的节点最终递归结束时返回的节点就是合并后链表的头节点最开始选择的最小节点。复杂度分析两种方法复杂度一致时间复杂度O(mn)O(m n)O(mn)其中m、n分别是两个链表的节点数。解释无论迭代还是递归每个节点都只被访问一次没有多余的比较操作时间复杂度与节点总数线性相关。空间复杂度迭代法O(1)O(1)O(1)仅使用了虚拟头节点和两个指针额外空间消耗为常数级无额外空间占用。递归法O(mn)O(m n)O(mn)递归调用会占用栈空间栈深度等于两个链表的总节点数最坏情况两个链表串联。总结迭代法更适合实际开发空间最优递归法适合理解递归思想面试中两种方法均可建议优先掌握迭代法。测试示例代码可直接运行为方便测试补充链表创建和打印函数可直接复制到本地运行验证测试代码# 辅助函数根据列表创建链表 def create_linked_list(arr): if not arr: return None head ListNode(arr[0]) curr head for val in arr[1:]: curr.next ListNode(val) curr curr.next return head # 辅助函数打印链表 def print_linked_list(head): res [] while head: res.append(str(head.val)) head head.next return -.join(res) # 测试示例1 list1 create_linked_list([1,2,4]) list2 create_linked_list([1,3,4]) merged Solution().mergeTwoLists(list1, list2) print(print_linked_list(merged)) # 输出1-1-2-3-4-4 # 测试示例2 list1 create_linked_list([]) list2 create_linked_list([]) merged Solution().mergeTwoLists(list1, list2) print(print_linked_list(merged)) # 输出空字符串 # 测试示例3 list1 create_linked_list([]) list2 create_linked_list([0]) merged Solution().mergeTwoLists(list1, list2) print(print_linked_list(merged)) # 输出0常见易错点提醒易错点1忘记处理“其中一个链表为空”的情况导致空指针异常。迭代法通过虚拟头节点、递归法通过终止条件规避易错点2拼接节点后忘记移动对应链表的指针如list1节点接入后未执行list1 list1.next导致死循环。易错点3递归法中返回值错误如忘记返回list1或list2导致合并后的链表断裂。易错点4合并后未保持升序本质是比较节点值时逻辑错误如将list1.val list2.val写成list1.val list2.val不影响结果但不符合题目“非递减”要求。总结合并两个有序链表是链表操作的经典基础题核心是利用“升序”特性通过“逐个比较、逐步拼接”的思路解决。迭代法通过虚拟头节点和指针遍历实现了空间最优是实际开发和面试中的首选递归法代码简洁能很好地体现分治思想适合巩固递归基础。本题难度适中重点掌握“虚拟头节点”的使用简化链表拼接和“递归终止条件”的设计后续可延伸到“合并k个有序链表”等进阶问题解题思路可复用。