题目
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
提示
一句话思路：递归——每次比较两个头节点，值较小的那个留下来，它的 next 指向剩余两个链表的合并结果。
- 递归终止条件：其中一个链表为空，直接返回另一个链表（剩余部分已有序，无需再排）。
- 每层递归只做一件事：比较
l1.val和l2.val，小的留下，大的和另一链表的剩余部分继续递归合并。 - 时间复杂度 O(m + n)，m、n 分别为两条链表长度；空间复杂度 O(m + n)（递归栈深度）。
答案
python
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1: # l1 为空，直接返回剩余的 l2
return l2
if not l2: # l2 为空，直接返回剩余的 l1
return l1
if l1.val <= l2.val: # l1 节点更小，l1 留下
l1.next = self.mergeTwoLists(l1.next, l2) # l1.next = 合并 l1 后段和 l2
return l1 # 返回当前 l1 节点
else: # l2 节点更小，l2 留下
l2.next = self.mergeTwoLists(l1, l2.next) # l2.next = 合并 l1 和 l2 后段
return l2 # 返回当前 l2 节点
留言板