LeetCode 21. 合并两个有序链表(Python)

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：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）和双指针来遍历两个链表，比较各自的节点值，将较小值的节点连接到新链表上，直至其中一个链表为空，最后将剩余部分直接接到新链表后面。

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    # 创建一个哑结点，方便返回结果链表
    dummy = ListNode(0)
    cur = dummy
    
    # 遍历两个链表，直到有一个为空
    while l1 and l2:
        if l1.val <= l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next
    
    # 将剩余部分接上
    cur.next = l1 if l1 else l2
    
    return dummy.next

代码解析
1. 初始化哑结点：
创建一个哑结点 dummy 并用 cur 指向该节点，方便在不需要处理头节点特殊情况的同时构造新的链表。
2. 双指针遍历：
使用 while l1 and l2 循环遍历两个链表。比较 l1 与 l2 当前节点的值，将较小的节点接到新链表的尾部，并移动对应链表的指针。
3. 接上剩余部分：
当其中一个链表遍历完毕后，另一个链表可能还有剩余节点，直接将剩余部分接到新链表末尾即可。
4. 返回结果：
最后返回 dummy.next，即合并后链表的头结点。

这种方法的时间复杂度为 O(n+m)，空间复杂度为 O(1)（不考虑输出链表所需空间）。

方法二：
递归方法的核心思想是：比较两个链表的头节点，较小的那个作为合并后链表的头，然后递归合并剩下的部分。

# 定义链表节点类
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    # 如果有一个链表为空，直接返回另一个链表
    if not l1:
        return l2
    if not l2:
        return l1
    
    # 递归调用时通过 self 调用类内的方法
    if l1.val <= l2.val:
        l1.next = self.mergeTwoLists(l1.next, l2)
        return l1
    else:
        l2.next = self.mergeTwoLists(l1, l2.next)
        return l2

代码解析
1. 递归终止条件
如果 l1 为空，则直接返回 l2；如果 l2 为空，则返回 l1。这保证了当其中一个链表遍历完时，递归能正确结束。
2. 递归比较
对于非空的 l1 和 l2，比较它们的值：
• 如果 l1.val 小于等于 l2.val，则将 l1 作为当前节点，并将 l1.next 指向递归合并后的结果。
• 否则，将 l2 作为当前节点，并将 l2.next 指向递归合并后的结果。
3. 返回结果
递归完成后，每一层调用都会返回合并后的链表头，最终返回整个合并后的链表。

这种方法同样能将两个升序链表合并为一个新的升序链表，时间复杂度为 O(n+m)，但使用了递归来实现。