040. 编写一个函数，合并两个有序链表

在 Python 中，合并两个有序链表可以通过迭代或递归的方式实现。

方法 1：迭代实现

迭代方法通过逐个比较两个链表的节点值，将较小的节点添加到新的链表中，直到其中一个链表为空。最后，将非空链表的剩余部分直接连接到新链表的末尾。

class ListNode:
    """
    定义链表的节点类。
    """
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def merge_two_lists(l1, l2):
    """
    使用迭代方法合并两个有序链表。

    参数:
        l1 (ListNode): 第一个有序链表的头节点。
        l2 (ListNode): 第二个有序链表的头节点。

    返回:
        ListNode: 合并后的有序链表的头节点。
    """
    # 创建一个虚拟头节点，方便操作
    dummy = ListNode()
    current = dummy

    # 遍历两个链表，直到其中一个链表为空
    while l1 and l2:
        if l1.value < l2.value:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    # 如果 l1 或 l2 中有一个非空，直接连接到新链表的末尾
    current.next = l1 if l1 else l2

    return dummy.next

# 测试代码
# 创建两个有序链表：1 -> 3 -> 5 和 2 -> 4 -> 6
l1 = ListNode(1, ListNode(3, ListNode(5)))
l2 = ListNode(2, ListNode(4, ListNode(6)))

# 合并两个有序链表
merged_head = merge_two_lists(l1, l2)

# 打印合并后的链表
current = merged_head
while current:
    print(current.value, end=" -> " if current.next else "")
    current = current.next

运行结果

运行上述代码后，输出如下：

1 -> 2 -> 3 -> 4 -> 5 -> 6

代码解释

创建虚拟头节点：

创建一个虚拟头节点 dummy，方便操作。current 指针初始化为 dummy。

迭代比较：

使用 while 循环，条件是 l1 和 l2 都不为空。
在每次循环中，比较 l1 和 l2 的当前节点值，将较小的节点连接到 current.next，并移动对应的指针。

连接剩余部分：

如果 l1 或 l2 中有一个非空，直接将剩余部分连接到 current.next。

返回结果：

返回 dummy.next，即合并后的链表的头节点。

方法 2：递归实现

递归方法通过递归调用合并两个链表的节点。每次递归调用处理一个节点，直到其中一个链表为空。

class ListNode:
    """
    定义链表的节点类。
    """
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def merge_two_lists_recursive(l1, l2):
    """
    使用递归方法合并两个有序链表。

    参数:
        l1 (ListNode): 第一个有序链表的头节点。
        l2 (ListNode): 第二个有序链表的头节点。

    返回:
        ListNode: 合并后的有序链表的头节点。
    """
    if not l1:
        return l2  # 如果 l1 为空，直接返回 l2
    if not l2:
        return l1  # 如果 l2 为空，直接返回 l1

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

# 测试代码
# 创建两个有序链表：1 -> 3 -> 5 和 2 -> 4 -> 6
l1 = ListNode(1, ListNode(3, ListNode(5)))
l2 = ListNode(2, ListNode(4, ListNode(6)))

# 合并两个有序链表
merged_head = merge_two_lists_recursive(l1, l2)

# 打印合并后的链表
current = merged_head
while current:
    print(current.value, end=" -> " if current.next else "")
    current = current.next

运行结果

运行上述代码后，输出如下：

1 -> 2 -> 3 -> 4 -> 5 -> 6

代码解释

递归终止条件：

如果 l1 为空，直接返回 l2。
如果 l2 为空，直接返回 l1。

递归调用：

比较 l1 和 l2 的当前节点值，将较小的节点的 next 指针指向递归调用的结果。
返回较小的节点作为当前节点。

返回结果：

返回递归调用的结果，即合并后的链表的头节点。

选择方法

迭代方法：

更高效，避免了递归调用的开销。
适用于大规模链表，不会导致栈溢出。

递归方法：

代码更简洁，易于理解。
适用于较小规模的链表，但需要注意递归深度。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)