当前位置: 首页 > news >正文

多个单链表的合成

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

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

输入格式:

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()
http://www.lryc.cn/news/454003.html

相关文章:

  • 『建议收藏』ChatGPT Canvas功能进阶使用指南!
  • Ollama 运行视觉语言模型LLaVA
  • gdb 调试 linux 应用程序的技巧介绍
  • Java项目实战II基于Java+Spring Boot+MySQL的房产销售系统(源码+数据库+文档)
  • aws(学习笔记第一课) AWS CLI,创建ec2 server以及drawio进行aws画图
  • 【Python】Eventlet 异步网络库简介
  • 【JNI】数组的基本使用
  • React跨平台
  • 如何在 SQL 中更新表中的记录?
  • 宠物饮水机的水箱低液位提醒如何实现?
  • EXCEL_光标百分比
  • (一)Web 网站服务之 Apache
  • 英语词汇小程序小程序|英语词汇小程序系统|基于java的四六级词汇小程序设计与实现(源码+数据库+文档)
  • AI学习指南深度学习篇-学习率衰减的实现机制
  • My_qsort() -自己写的 qsort 函数
  • 《向量数据库指南》——Mlivus Cloud打造生产级AI应用利器
  • Electron 进程通信
  • Kubernetes资源详解
  • C++11之线程
  • 界星空科技漆包线行业称重系统
  • RabbitMQ的高级特性-事务
  • Qt Linguist手册
  • 【简介Sentinel-1】
  • 第 17 场小白入门赛蓝桥杯
  • @antv/x6 导出图片下载,或者导出图片为base64由后端去处理。
  • 从零到精通:AI大模型的全方位学习路径解析,非常详细收藏我这一篇就够了
  • PowerShell脚本在自动化Windows开发工作流程中的应用
  • 【力扣 | SQL题 | 每日四题】力扣1783,1757,1747,1623,1468,1661
  • 《深入探究 C++中的函数模板特化:开启编程新境界》
  • RTEMS面试题汇总及参考答案