网站建设万首先金手指14,wordpress二维码手工,ASP.NET实用网站开发答案,网站后台程序如何做建立两个非递减有序单链表#xff0c;然后合并成一个非递增有序的单链表。
注意#xff1a;建立非递减有序的单链表#xff0c;需要采用创建单链表的算法
输入格式:
1 9 5 7 3 0
2 8 4 6 0
输出格式:
9 8 7 6 5 4 3 2 1
输入样例:
在这里给出一组输入。例如#xf…建立两个非递减有序单链表然后合并成一个非递增有序的单链表。
注意建立非递减有序的单链表需要采用创建单链表的算法
输入格式:
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, dataNone):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()
