Python 链表合并算法实现

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

class LinkedList:
    def __init__(self):
        self.head = None

    def add(self, val):
        node = Node(val)
        if self.head is None:
            self.head = node
        else:
            curr = self.head
            while curr.next is not None:
                curr = curr.next
            curr.next = node

    def merge(self, b):
        a_curr = self.head
        b_curr = b.head
        merged_list = LinkedList()

        while a_curr is not None and b_curr is not None:
            if a_curr.val < b_curr.val:
                merged_list.add(a_curr.val)
                a_curr = a_curr.next
            else:
                merged_list.add(b_curr.val)
                b_curr = b_curr.next

        while a_curr is not None:
            merged_list.add(a_curr.val)
            a_curr = a_curr.next

        while b_curr is not None:
            merged_list.add(b_curr.val)
            b_curr = b_curr.next

        return merged_list

# 创建两个链表
lst1 = LinkedList()
lst1.add(1)
lst1.add(3)
lst1.add(5)

lst2 = LinkedList()
lst2.add(2)
lst2.add(4)
lst2.add(6)

# 合并两个链表
merged_lst = lst1.merge(lst2)

# 打印合并后的链表
curr = merged_lst.head
while curr is not None:
    print(curr.val)
    curr = curr.next

# 输出结果为：1 2 3 4 5 6

算法逻辑

1. 创建一个新的链表 merged_list 来存储合并后的结果。
2. 使用两个指针 a_curr 和 b_curr 分别指向两个输入链表的头结点。
3. 比较 a_curr 和 b_curr 指向的节点的值，将较小的值添加到 merged_list 中，并将对应的指针移向下一个节点。
4. 重复步骤 3 直到其中一个链表的指针到达链表的末尾。
5. 将剩余的链表中的节点全部添加到 merged_list 中。
6. 返回 merged_list。

代码示例

以上代码示例展示了如何使用 Python 实现链表合并算法，并通过创建两个链表并合并它们来演示算法的实际应用。代码简洁易懂，方便理解和学习。

总结

链表合并算法是数据结构和算法中常用的算法之一，它可以有效地将两个有序链表合并成一个新的有序链表。本篇文章介绍了使用 Python 实现该算法的代码示例，并解释了算法逻辑，希望能帮助读者更好地理解和运用该算法。