1161 Merging Linked Lists (25)
Given two singly linked lists L1=a1→a2→⋯→an−1→an and L2=b1→b2→⋯→bm−1→bm. If n≥2m, you are supposed to reverse and merge the shorter one into the longer one to obtain a list like a1→a2→bm→a3→a4→bm−1⋯. For example, given one list being 6→7 and the other one 1→2→3→4→5, you must output 1→2→7→3→4→6→5.
Input Specification:
Each input file contains one test case. For each case, the first line contains the two addresses of the first nodes of L1 and L2, plus a positive N (≤105) which is the total number of nodes given. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1
.
Then N lines follow, each describes a node in the format:
Address Data Next
where Address
is the position of the node, Data
is a positive integer no more than 105, and Next
is the position of the next node. It is guaranteed that no list is empty, and the longer list is at least twice as long as the shorter one.
Output Specification:
For each case, output in order the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.
Sample Input:
00100 01000 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1
Sample Output:
01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1
题目大意:给定两个单链表L1 = a1 → a2 → … → an-1 → an,和L2 = b1 → b2 → … → bm-1 → bm,将较短的那个链表逆序,然后将之并入比较长的那个链表,得到一个形如a1 → a2 → bm → a3 → a4 → bm-1 … 的结果,例如给定两个链表分别为6→7和1→2→3→4→5,你应该输出1→2→7→3→4→6→5。
分析:由于题目没有说哪个链表更长,因此首先要先确定短的链表是哪个,再把短的链表逆序。之后长的链表每前进2步,短的链表前进1步。注意有可能n=2*m的边界条件。
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <stack>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#define INF 0xffffffff
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<endl
#define db5(x,y,z,r,w) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<", "<<#w<<"="<<(w)<<endl
using namespace std;typedef struct node
{int val,next,id;
}node;int main(void)
{#ifdef testfreopen("in.txt","r",stdin);//freopen("in.txt","w",stdout);clock_t start=clock();#endif //testint r1,r2,n;scanf("%d%d%d",&r1,&r2,&n);node num[100000];for(int i=0;i<100000;++i)num[i].val=0,num[i].next=-1,num[i].id=i;for(int i=0;i<n;++i){int a,b,c;scanf("%d%d%d",&a,&b,&c);num[a].val=b,num[a].next=c;}int t1=0,t2=0,pos1=r1,pos2=r2;while(pos1!=-1)t1++,pos1=num[pos1].next;while(pos2!=-1)t2++,pos2=num[pos2].next;if(t1<t2)swap(r1,r2);pos1=r1,pos2=r2;int temp=-1,next=-1;while(pos2!=-1){if(num[pos2].next==-1)r2=pos2;next=num[pos2].next,num[pos2].next=temp,temp=pos2,pos2=next;}// pos2=r2;
// while(pos2!=-1)
// {
// printf("%05d %d %05d\n",num[pos2].id,num[pos2].val,num[pos2].next);
// pos2=num[pos2].next;
// }printf("\n");pos2=r2;int t=0;while(pos1!=-1){if(t<2||pos2==-1){if(pos1==r1)printf("%05d %d",num[pos1].id,num[pos1].val);else printf(" %05d\n%05d %d",num[pos1].id,num[pos1].id,num[pos1].val);t++;pos1=num[pos1].next;}else{printf(" %05d\n%05d %d",num[pos2].id,num[pos2].id,num[pos2].val);pos2=num[pos2].next;t=0;}}if(pos2!=-1)printf(" %05d\n%05d %d",num[pos2].id,num[pos2].id,num[pos2].val);pos2=num[pos2].next;t=0;printf(" -1\n");#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl; //s为单位cout<<"Total time:"<<endtime*1000<<"ms"<<endl; //ms为单位#endif //testreturn 0;
}
相关文章:
1161 Merging Linked Lists (25)
Given two singly linked lists L1a1→a2→⋯→an−1→an and L2b1→b2→⋯→bm−1→bm. If n≥2m, you are supposed to reverse and merge the shorter one into the longer one to obtain a list like a1→a2→bm→a3→a4→bm−1⋯. For ex…...
内联变量(inline variables):在多个文件中共享全局常量
在 C17 中,引入了 内联变量(inline variables) 的概念,可以用于在多个文件中共享全局常量。内联变量允许在头文件中定义变量,而不会导致链接错误(如重复定义)。这种方式非常适合用于定义跨多个文…...

Jmeter进行http接口并发测试
目录: 1、Jmeter设置(1)设置请求并发数(2)设置请求地址以及参数(3)添加结果数 2、启动看结果 1、Jmeter设置 (1)设置请求并发数 (2)设置请求地址…...
力扣解题汇总_JAVA
文章目录 数学_简单13_罗马数字转整数66_ 加一9_回文数70_爬楼梯69_x的平方根509_斐波那契数列2235_两整数相加67_二进制求和415_字符串相加2413_最小偶倍数2469_温度转换704_二分查找(重点) 数组_简单1_两数之和88_合并两个有序数组 链表_简单21_合并两个有序链表203_移除链表…...
ubuntu下安装编译cmake,grpc与protobuf
文章目录 install cmakeinstall grpcinstall protobuf注 install cmake sudo apt-get install -y g make libssl-devcd third_party/cmake-3.17.2./configuresudo make && make installcmake --version install grpc $ sudo apt-get install -y build-essential auto…...

SQL Prompt 插件
SQL Prompt 插件 注:SQL Prompt插件提供智能代码补全、SQL格式化、代码自动提示和快捷输入等功能,非常方便,可以自行去尝试体会。 1、问题 SSMS(SQL Server Management Studio)是SQL Server自带的管理工具,…...

知识图谱抽取分析中,如何做好实体对齐?
在知识图谱抽取分析中,实体对齐是将不同知识图谱中的相同实体映射到同一表示空间的关键步骤。为了做好实体对齐,可以参考以下方法和策略: 基于表示学习的方法: 使用知识图谱嵌入技术,如TransE、GCN等,将实体…...

【Python通过UDP协议传输视频数据】(界面识别)
提示:界面识别项目 前言 随着网络通信技术的发展,视频数据的实时传输在各种场景中得到了广泛应用。UDP(User Datagram Protocol)作为一种无连接的协议,凭借其低延迟、高效率的特性,在实时性要求较高的视频…...

【伪随机数】关于排序算法自测如何生成随机数而引发的……
以 Random 开始 可能一开始,你只是写到了排序算法如何生成随机数 public static void main(String[] args) {Random random new Random();int[] nums new int[10];for (int i 0; i < nums.length; i) {nums[i] random.nextInt(100);}System.out.println(&q…...
核密度估计(Kernel Density Estimation, KDE)是一种非参数统计方法
一、核密度估计 核密度估计(Kernel Density Estimation, KDE)是一种非参数统计方法,用于估计随机变量的概率密度函数。它通过将每个数据点周围的核函数叠加,生成平滑的密度曲线。以下是其核心要点: 1. 基本概念 非参…...

【k8s面试题2025】2、练气初期
在练气初期,灵气还比较稀薄,只能勉强在体内运转几个周天。 文章目录 简述k8s静态pod为 Kubernetes 集群移除新节点:为 K8s 集群添加新节点Kubernetes 中 Pod 的调度流程 简述k8s静态pod 定义 静态Pod是一种特殊类型的Pod,它是由ku…...

栈溢出原理
文章目录 前言一、基本示例二、分析栈1. 先不考虑gets函数的栈情况2. 分析gets函数的栈区情况 三、利用栈1. 构造字符串2. 利用漏洞 前言 栈溢出指的是程序向栈中某个变量中写入的字节数超过了这个变量本身所申请的字节数,因而导致与其相邻的栈中的变量的值被改变。…...

Jmeter如何进行多服务器远程测试
🍅 点击文末小卡片 ,免费获取软件测试全套资料,资料在手,涨薪更快 JMeter是Apache软件基金会的开源项目,主要来做功能和性能测试,用Java编写。 我们一般都会用JMeter在本地进行测试,但是受到单…...
2.slf4j入口
文章目录 一、故事引入二、原理探究三、SLF4JServiceProvider四、总结 一、故事引入 故事要从下面这段代码说起 public class App {private static final Logger logger LoggerFactory.getLogger(App.class);public static void main( String[] args ) throws Exception {lo…...

初学stm32 --- CAN
目录 CAN介绍 CAN总线拓扑图 CAN总线特点 CAN应用场景 CAN物理层 CAN收发器芯片介绍 CAN协议层 数据帧介绍 CAN位时序介绍 数据同步过程 硬件同步 再同步 CAN总线仲裁 STM32 CAN控制器介绍 CAN控制器模式 CAN控制器模式 CAN控制器框图 发送处理 接收处理 接收过…...

软件测试—接口测试面试题及jmeter面试题
一,接口面试题 1.接口的作用 实现前后端的交互,实现数据的传输 2.什么是接口测试 接口测试就是对系统或组件之间的接口进行测试,主要是校验数据的交换、传递和控制管理过程,以及相互逻辑关系 3.接口测试必要性 1.可以发现很…...

图论的起点——七桥问题
普瑞格尔河从古堡哥尼斯堡市中心流过,河中有小岛两座,筑有7座古桥,哥尼斯堡人杰地灵,市民普遍爱好数学。1736年,该市一名市民向大数学家Euler提出如下的所谓“七桥问题”: 从家里出发,7座桥每桥…...
嵌入式开发通讯协议大全(在写中)
目录 modbus RTU通讯协议: pmbus通讯协议: modbus RTU通讯协议: 主要应用功能: 规范了软件变量,访问功能码,给不同工程师开发的不同产品有统一的通讯标准 帧结构简单,占用带宽少,…...
webpack 4 升级 webpack 5
升级至最新的 webpack 和 webpack-cli npm run build 报错, unknown option -p 解决方案: 改成 --mode production npm run build 报错 unknown option --hide-modules 解决方案:直接移除 npm run build 报错:TypeError: Cannot a…...
oneplus3t-lineageos-16.1编译-android9, oneplus3t-lineage-14编译-android7
oneplus3t-lineage-14编译-android7 1 清华linageos镜像 x lineage-14.1-20180223-nightly-oneplus3-signed.zip ntfs分区挂载为普通用户目录 , ext4分区挂载为普通用户目录 bfsu/lineageOS镜像 ts/lingeageOS镜像 oneplus3/lineage-build-simple-manual.md, manifest-p…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...

CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...