手把手带你学算法——合并两个有序链表（21）

        欢迎来到本教程的一篇新文章，今天我们将学习如何解决LeetCode中的问题21——"合并两个有序链表"。这是一个非常基础且实用的链表问题，通过学习如何解决它，你将掌握如何操作链表并解决类似问题。

问题描述

题目描述如下：

合并两个有序链表并将其作为一个新链表返回。新链表应该由输入的两个链表的节点组成。

示例：

假设我们有两个有序链表 1 -> 2 -> 4 和 1 -> 3 -> 4，合并后的链表应该是 1 -> 1 -> 2 -> 3 -> 4 -> 4。

解决思路

要解决这个问题，我们可以使用迭代方法或递归方法。下面是迭代方法的解决思路：

1. 创建一个新的链表 merged 用于存储合并后的结果。

2. 初始化三个指针 l1、l2 和 current，分别指向两个有序链表的头节点以及 merged 的尾节点。

3. 在每次迭代中，比较 l1 和 l2 的当前节点的值，将较小的值添加到 merged 链表的尾部，并将相应的指针向前移动。

4. 重复上述步骤，直到 l1 或 l2 中的一个为空。

5. 最后，将 l1 或 l2 中剩余的节点添加到 merged 的尾部，返回合并后的链表。

Python代码实现

下面是使用Python实现的解决方案代码：

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

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        merged = ListNode(0)
        current = merged

        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

        current.next = l1 or l2

        return merged.next

示例

现在让我们看一个示例，演示如何使用这个算法来合并两个有序链表：

# 创建两个有序链表：1 -> 2 -> 4 和 1 -> 3 -> 4
l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(4)

l2 = ListNode(1)
l2.next = ListNode(3)
l2.next.next = ListNode(4)

# 合并两个有序链表
solution = Solution()
merged_list = solution.mergeTwoLists(l1, l2)

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

输出应该是：

1 -> 1 -> 2 -> 3 -> 4 -> 4 ->

结论

通过这篇教程，我们学习了如何解决LeetCode问题21——"合并两个有序链表"，并提供了相应的Python代码示例。希望这个教程帮助你理解如何操作链表并解决链表合并问题。在接下来的教程中，我们将继续学习更多有关数据结构和算法的知识。感谢阅读！