16 合并两个排序的链表

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

示例：

输入: 1->3->5, 2->4->6
输出: 1->2->3->4->5->6

输入: 1->2->3, None
输出: 1->2->3

解题思路

方法一：迭代

核心思想：使用虚拟头节点，依次比较两个链表的节点，较小的先加入结果链表。

方法二：递归

核心思想：比较两个头节点，较小的作为新头，递归合并剩余部分。

时间复杂度：O(m + n) 空间复杂度：O(1)（迭代）或 O(m + n)（递归栈）

Python 实现

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# 方法一：迭代
def merge_two_lists(l1, l2):
    """
    合并两个排序链表（迭代）
    """
    # 虚拟头节点
    dummy = ListNode(0)
    curr = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next

    # 连接剩余部分
    curr.next = l1 if l1 else l2

    return dummy.next


# 方法二：递归
def merge_two_lists_recursive(l1, l2):
    """
    合并两个排序链表（递归）
    """
    if not l1:
        return l2
    if not l2:
        return l1

    if l1.val <= l2.val:
        l1.next = merge_two_lists_recursive(l1.next, l2)
        return l1
    else:
        l2.next = merge_two_lists_recursive(l1, l2.next)
        return l2


# 辅助函数：创建链表
def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    p = head
    for val in arr[1:]:
        p.next = ListNode(val)
        p = p.next
    return head


# 辅助函数：打印链表
def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print('->'.join(result))


# 测试代码
if __name__ == "__main__":
    # 创建链表
    l1 = create_linked_list([1, 3, 5])
    l2 = create_linked_list([2, 4, 6])

    print("链表1: ", end="")
    print_list(l1)
    print("链表2: ", end="")
    print_list(l2)

    merged = merge_two_lists(l1, l2)
    print("合并后: ", end="")
    print_list(merged)

    # 测试递归版本
    l3 = create_linked_list([1, 2, 3])
    l4 = create_linked_list([])
    print("\n链表3: ", end="")
    print_list(l3)
    print("链表4: ", end="")
    print_list(l4)

    merged2 = merge_two_lists_recursive(l3, l4)
    print("递归合并后: ", end="")
    print_list(merged2)

# 输出:
# 链表1: 1->3->5
# 链表2: 2->4->6
# 合并后: 1->2->3->4->5->6
#
# 链表3: 1->2->3
# 链表4:
# 递归合并后: 1->2->3

图解

迭代合并示例:
l1: 1->3->5->None
l2: 2->4->6->None

步骤1: 1 < 2, 取1
dummy→1
      ↑curr
l1: 3->5, l2: 2->4->6

步骤2: 3 > 2, 取2
dummy→1→2
         ↑curr
l1: 3->5, l2: 4->6

步骤3: 3 < 4, 取3
dummy→1→2→3
           ↑curr
l1: 5, l2: 4->6

步骤4: 5 > 4, 取4
...

最终: dummy→1→2→3→4->5->6
返回: dummy.next