def Merge2(A,B):
p=A.head.next
q=B.head.next
C=LinkList()
t=C.head
while p!=None and q!=None:
if p.data<q.data:
t.next=p
t=p
p=p.next
elif p.data==q.data:
t.next=p
t=p
q=q.next
p=p.next
else:
t.next=q
t=q
q=q.next
t.next=None
if p!=None:
t.next=p
if q!=None:
t.next=q
return C
A=LinkList()
B=LinkList()
A.CreateListR([1,3,5,7])
B.CreateListR([1,2,4,5,7])
A.display()
B.display()}
C=Merge2(A,B)
C.display()
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_at_end(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
# 计算两个链表的并集
def union(self, list1, list2):
s = set()
current_node = list1.head
while current_node:
s.add(current_node.data)
current_node = current_node.next
current_node = list2.head
while current_node:
s.add(current_node.data)
current_node = current_node.next
new_list = LinkedList()
for element in s:
new_list.insert_at_end(element)
return new_list
def print_list(self):
if self.head is None:
print("List is empty.")
return
current_node = self.head
while current_node:
print(current_node.data, end=" ")
current_node = current_node.next
list1 = LinkedList()
list1.insert_at_end(1)
list1.insert_at_end(2)
list1.insert_at_end(3)
list2 = LinkedList()
list2.insert_at_end(3)
list2.insert_at_end(4)
list2.insert_at_end(5)
new_list = LinkedList().union(list1, list2)
print("Union of list1 and list2 : ", end="")
new_list.print_list()
前两步完成后的数组并不包括所有结果，因为不交换元素位置也是一种排列，所以在每次交换元素后，都应该分支出两种选择：交换和不交换。因为要得到所有结果，循环次数远远不够，此时想到递归所有位置。