【2019秋PAT乙级真题】7-5 链表合并 (25 分)
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://cloud.tencent.com/developer/article/1535004
7-5 链表合并 (25 分)
给定两个单链表 L1=a1→a2→⋯→an−1→an 和 L2=b1→b2→⋯→bm−1→bm。如果 n≥2m，你的任务是将比较短的那个链表逆序，然后将之并入比较长的那个链表，得到一个形如 a1→a2→bm→a3→a4→bm−1⋯ 的结果。例如给定两个链表分别为 6→7 和 1→2→3→4→5，你应该输出 1→2→7→3→4→6→5。
输入格式：
输入首先在第一行中给出两个链表 L1 和 L2 的头结点的地址，以及正整数 N (≤105)，即给定的结点总数。一个结点的地址是一个 5 位数的非负整数，空地址 NULL 用 -1 表示。
随后 N 行，每行按以下格式给出一个结点的信息：
Address Data Next
其中 Address 是结点的地址，Data 是不超过 105 的正整数，Next 是下一个结点的地址。题目保证没有空链表，并且较长的链表至少是较短链表的两倍长。
输出格式：
按顺序输出结果链表，每个结点占一行，格式与输入相同。
输入样例：
00100 01000 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1
输出样例：
01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1
PAT这种题型出现了好几遍了。。。链表相关的题
我都是直接输出 地址换行地址 数据这种格式输出每个节点。。
一般情况下都会卡一下细节，这次考试都是一遍就过了（万万没想到25分的一旦简单了 20分的就会卡死）
#include<iostream>
using namespace std;
struct Lian{
int id;
int data;
int next;
};
Lian lian[100005];
Lian lian1[100005];
Lian lian2[100005];
int main(){
int l1,l2,n;
cin>>l1>>l2>>n;
int id,data,next;
for(int i=0;i<n;i++){
cin>>id>>data>>next;
lian[id].id=id;
lian[id].next=next;
lian[id].data=data;
}int p=l1;
int n1=0,n2=0;
while(p!=-1){
lian1[n1++]=lian[p];
p=lian[p].next;
}p=l2;
while(p!=-1){
lian2[n2++]=lian[p];
p=lian[p].next;
}
int flag=0;
if(n1>=2*n2){
int g=0;
n2--;
while(g<n1||n2>0){
if(g<n1){
if(flag==0){
printf("%05d %d ",lian1[g].id,lian1[g].data);
g++;
}else{
printf("%05d\n%05d %d ",lian1[g].id,lian1[g].id,lian1[g].data);
g++;
}
}
flag=1;
if(g<n1){
printf("%05d\n%05d %d ",lian1[g].id,lian1[g].id,lian1[g].data);
g++;
}
if(n2>=0){
printf("%05d\n%05d %d ",lian2[n2].id,lian2[n2].id,lian2[n2].data);
n2--;
}
}
cout<<"-1";
}else{
int g=0;
n1--;
while(g<n2||n1>0){
if(g<n2){
if(flag==0){
printf("%05d %d ",lian2[g].id,lian2[g].data);
g++;
}else{
printf("%05d\n%05d %d ",lian2[g].id,lian2[g].id,lian2[g].data);
g++;
}
}
flag=1;
if(g<n2){
printf("%05d\n%05d %d ",lian2[g].id,lian2[g].id,lian2[g].data);
g++;
}
if(n1>=0){
printf("%05d\n%05d %d ",lian1[n1].id,lian1[n1].id,lian1[n1].data);
n1--;
}
}
cout<<"-1";
}
return 0;
}腾讯云开发者
