合并两个已排序链表

本文将概述合并两个已排序链表算法并提供 Python 实现。

链表是计算机科学和编程中的基本数据结构。它们提供了一种高效的方式来存储和组织非连续的数据。链表由包含数据和指向下一个节点引用的节点组成。这允许高效地将节点插入或删除到列表中的任何位置。

链表的一个常见应用是维护已排序的数据。给定两个已排序的链表，通常需要将它们有效地合并成一个已排序的链表。这个合并后的列表包含两个输入列表的所有数据，并按排序顺序排列。

合并两个已排序链表的算法是一个重要的算法，经常出现在编码面试和编程练习中。它展示了核心的链表操作，并结合了迭代、指针操作和排序算法基础等概念。

算法和 Python 实现

1. 初始化两个指针变量 p1 和 p2，它们指向两个链表的头节点。
2. 初始化一个指针变量 p3，它将最终指向合并链表的头节点。
3. 初始化一个指针变量 prev_node 来跟踪 p3 之前的节点。
4. 比较 p1 和 p2 指向的节点中的数据值。
5. 如果 p1 的数据较小，则将 prev_node 设置为 p1，并将 p1 移动到下一个节点。
6. 否则，如果 p2 的数据较小，则将 prev_node 设置为 p2，并将 p2 移动到下一个节点。
7. 否则，如果数据相等，则将 prev_node 设置为 p1，将 p1 移动到下一个节点，将 prev_node.next 设置为 p2，然后将 p2 移动到下一个节点。
8. 一旦 prev_node 更新，就更新 p3 使其指向 prev_node 所指向的节点。这会将 p3 设置为头节点。
9. 重复步骤 4-8，直到我们到达一个或两个列表的末尾。
10. 如果 p1 首先到达末尾，则将剩余的 p2 列表附加到 p3 列表的末尾。如果 p2 首先到达末尾，则附加 p1 列表。
11. 返回头节点 p3。

该算法遍历两个列表，在每次迭代中比较数据，并将节点按排序顺序链接起来以构建合并列表。时间复杂度为 O(n)，其中 n 是两个列表中的节点数。这是一种合并两个已排序列表的高效方法。

下面是一个 Python 实现示例

Python 程序

说明

1. 定义一个 Node 类来存储数据和指向下一个节点的指针。
2. 定义一个 LinkedList 类，其中包含 head 节点、append 和 printList 方法。
3. append 方法创建一个新节点并将其附加到列表的末尾。
4. printList 打印列表中所有节点的数据。
5. mergeLists 函数以两个列表的头节点作为参数。
6. 创建一个虚拟节点来构建合并列表。
7. 初始化 tail 指向虚拟节点，以跟踪合并列表的末尾。
8. 初始化 p1 和 p2 指针指向每个列表的头部。
9. 循环直到其中一个列表为空。
10. 比较 p1 和 p2 的数据。将较小的数据节点附加到 tail。
11. 相应地推进 p1 或 p2 指针。
12. 将 tail 推进到新附加的节点。
13. 循环结束后，附加 p1 或 p2 中剩余的任何节点。
14. 返回虚拟节点之后的下一个节点，即合并列表的头部。
15. 测试用例创建两个示例列表，并使用 mergeLists 函数合并它们。
16. 使用 printList 打印合并列表的数据。