Python实现两个整数单链表的并集算法

有两个集合采用整数单链表A、B存储，设计一个算法求两个集合的并集C，C仍然用单链表存储，并给出算法的时间和空间复杂度。例如 A=(1,3,2)，B=(5,1,4,2)，并集C=(1,3,2,5,4)。

算法思路：

创建一个空的单链表C
遍历A链表，将A链表中的元素添加到C链表中
遍历B链表，将B链表中的元素添加到C链表中，如果该元素在C链表中已经存在，则不添加
返回C链表

时间和空间复杂度

时间复杂度：O(n)，n为A和B链表中元素的总数
空间复杂度：O(n)，需要创建一个新的链表来存储并集C

Python代码实现：

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
def union(A, B):
    C = Node()
    tail = C
    dict = {}
    p = A.next
    while p:
        tail.next = Node(p.val)
        tail = tail.next
        dict[p.val] = 1
        p = p.next
    p = B.next
    while p:
        if p.val not in dict:
            tail.next = Node(p.val)
            tail = tail.next
        p = p.next
    return C.next

# 测试
A = Node()
A.next = Node(1, Node(3, Node(2)))
B = Node()
B.next = Node(5, Node(1, Node(4, Node(2))))
C = union(A, B)
p = C
while p:
    print(p.val, end=' ')
    p = p.next
# 输出：1 3 2 5 4

代码解析

Node 类定义了单链表的节点，包含 val 和 next 属性，分别表示节点的值和下一个节点的引用。
union 函数接收两个单链表 A 和 B 作为参数，返回它们的并集 C。
函数首先创建一个空的节点 C 作为并集链表的头节点。
使用 tail 指针指向当前链表的尾部，方便添加新的节点。
使用 dict 字典来记录已经添加到 C 链表中的元素，避免重复添加。
遍历 A 链表，将每个元素添加到 C 链表中，并将元素的值作为键添加到 dict 中。
遍历 B 链表，如果元素不在 dict 中，则将其添加到 C 链表中。
最后返回 C 链表的头节点 C.next。

代码测试

在测试代码中，我们创建了两个链表 A 和 B，分别表示集合 (1, 3, 2) 和 (5, 1, 4, 2)。然后调用 union 函数计算它们的并集 C，并打印输出结果，结果为 1 3 2 5 4，即两个链表的并集。

总结

本文介绍了如何使用Python实现两个整数单链表的并集算法，并给出了算法的详细代码实现和测试用例。该算法利用字典存储已存在元素，避免重复添加，时间复杂度为O(n)，空间复杂度为O(n)。