多个单链表的合成

建立两个非递减有序单链表，然后合并成一个非递增有序的单链表。

注意：建立非递减有序的单链表，需要采用创建单链表的算法

输入格式:

1 9 5 7 3 0

2 8 4 6 0

输出格式:

9 8 7 6 5 4 3 2 1

输入样例:

在这里给出一组输入。例如：

2 8 4 6 3 7 0
-4 5 6 2 3 9 0

输出样例:

在这里给出相应的输出。例如：

9 8 7 6 6 5 4 3 3 2 2 -4

# 定义链表节点类
class Node:def __init__(self, data=None):self.data = dataself.next = None# 定义单向链表类
class LinkedList:def __init__(self):self.head = Node()  # 初始化头结点# 有序插入节点到非递减链表中def insert(self, data):new_node = Node(data)cur = self.head# 找到插入位置: cur.next 为第一个大于 data 的节点while cur.next and cur.next.data < data:cur = cur.nextnew_node.next = cur.nextcur.next = new_node# 合并两个非递减链表，并返回合并后的链表def merge(self, other):merged_list = LinkedList()  # 创建新的合并链表cur1 = self.head.next  # 跳过头结点cur2 = other.head.next  # 跳过头结点# 合并两个链表while cur1 and cur2:if cur1.data <= cur2.data:merged_list.insert(cur1.data)cur1 = cur1.nextelse:merged_list.insert(cur2.data)cur2 = cur2.next# 处理剩余的元素while cur1:merged_list.insert(cur1.data)cur1 = cur1.nextwhile cur2:merged_list.insert(cur2.data)cur2 = cur2.nextreturn merged_list# 反转链表def reverse(self):prev = Nonecur = self.head.next  # 跳过头结点while cur:next_node = cur.next  # 保存下一个节点cur.next = prev  # 反转指针prev = cur  # 移动 prevcur = next_node  # 移动 curself.head.next = prev  # 更新头结点的next指针# 打印链表的所有元素def display(self):cur = self.head.next  # 跳过头结点while cur:print(cur.data, end=" ")cur = cur.nextprint()# 主程序
def main():# 建立第一个链表linked_list1 = LinkedList()input1 = input().split()for num in input1:num = int(num)if num == 0:breaklinked_list1.insert(num)# 建立第二个链表linked_list2 = LinkedList()input2 = input().split()for num in input2:num = int(num)if num == 0:breaklinked_list2.insert(num)# 合并两个有序链表merged_list = linked_list1.merge(linked_list2)# 反转合并后的链表以变为非递增顺序merged_list.reverse()# 打印反转后的链表merged_list.display()# 调用主程序
main()