Python 实现有序链表合并：链式存储方式详解

本文将介绍如何使用链式存储方式实现线性表，并提供 Python 代码演示两个有序链表的合并过程。代码涵盖了建立链表、合并链表和输出链表等功能，并解释了每个函数的实现细节。

代码实现

# 定义链表节点类
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

# 建立链表函数
def create_linked_list(nums):
    head = Node()
    cur = head
    for num in nums:
        cur.next = Node(num)
        cur = cur.next
    return head.next

# 合并链表的函数
def merge_linked_lists(list1, list2):
    dummy = Node()
    cur = dummy
    while list1 and list2:
        if list1.data <= list2.data:
            cur.next = list1
            list1 = list1.next
        else:
            cur.next = list2
            list2 = list2.next
        cur = cur.next
    if list1:
        cur.next = list1
    if list2:
        cur.next = list2
    return dummy.next

# 输出链表中所有数据的函数
def print_linked_list(head):
    cur = head
    while cur:
        print(cur.data)
        cur = cur.next

# 主函数
if __name__ == "__main__":
    # 建立两个有序链表
    list1 = create_linked_list([1, 3, 5, 7, 9])
    list2 = create_linked_list([2, 4, 6, 8, 10])

    # 合并链表
    merged_list = merge_linked_lists(list1, list2)

    # 输出合并后的链表中所有数据
    print_linked_list(merged_list)

代码解析

1. 链表节点类

Node 类定义了链表节点的基本结构，包含数据域 data 和指向下一个节点的指针 next。

2. 建立链表函数

create_linked_list 函数接受一个列表作为参数，将列表中的元素依次构建成链表节点，并返回链表的头节点。

3. 合并链表函数

merge_linked_lists 函数接受两个有序链表作为参数，并返回一个新的有序链表，该链表包含两个输入链表的所有元素，并保持升序排列。

函数首先创建一个哑节点 dummy，用于简化操作。然后，使用两个指针 cur 和 list1、list2 分别遍历两个输入链表，将较小的节点插入到 dummy 后面。最后，将剩余的节点插入到 dummy 后面，并返回 dummy 的下一个节点。

4. 输出链表函数

print_linked_list 函数接受链表的头节点作为参数，并依次输出链表中所有节点的数据。

5. 主函数

主函数 if __name__ == "__main__" 中创建了两个有序链表，并调用 merge_linked_lists 函数合并两个链表。最后，调用 print_linked_list 函数输出合并后的链表中所有数据。

输出结果

总结

本文介绍了如何使用链式存储方式实现线性表，并提供了 Python 代码演示两个有序链表的合并过程。该代码简洁易懂，并包含了详细的解释，方便读者学习和理解。希望本文能帮助读者更好地理解链表的实现和应用。