有两个集合采用整数单链表A、B存储设计一个算法求两个集合的并集CC仍然用单链表存储并给出算法的时间和空间复杂度。例如 A=132B=5142并集C=13254。用python实现

算法思路：

1. 创建一个空的单链表C
2. 遍历A链表，将A链表中的元素添加到C链表中
3. 遍历B链表，将B链表中的元素添加到C链表中，如果该元素在C链表中已经存在，则不添加
4. 返回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