一共不超过10^5个结点 直接用个数组存 索引表示地址
#include<iostream>
#include<vector>
using namespace std;
const int N=100010;
int ha,hb,n;
int w[N],ne[N],idx;
vector<int> la,lb;//存链表的每个结点的地址(也就是索引)
int main(){
cin>>ha>>hb>>n;
while(n--){
scanf("%d",&idx);
scanf("%d %d",&w[idx],&ne[idx]);
}
//将每个结点的地址存一下 其实链表a的地址都不用存 直接拿个指针指就行
for(int i=ha;~i;i=ne[i])la.push_back(i);
for(int i=hb;~i;i=ne[i])lb.push_back(i);
//保证la是较长的
if(la.size()<lb.size())swap(la,lb);
int q=0,p=lb.size()-1;//q从小到大 表示从前向后 p从大到小表示从后向前
while(~p){
//i1 i2 i3分别表示打印的三个结点的地址
int i1=la[q],i2=la[q+1],i3=lb[p];//一次打印三个 la正着打印两个 lb倒着打印一个
printf("%05d %d %05d\n",i1,w[i1],i2);
printf("%05d %d %05d\n",i2,w[i2],i3);
//只有第三个打印可能出现-1的情况 也就是n==2m的时候
if(ne[i2]==-1)//为了-1的格式 c++的输出只会一点点
printf("%05d %d -1\n",i3,w[i3]);
else
printf("%05d %d %05d\n",i3,w[i3],ne[i2]);
q+=2,p--;//q向后位移两个
}
for(;q<la.size();q++){//b输完了 a链表可能还有
int idx=la[q];
if(ne[idx]==-1)//为了-1的格式 否则会输出-0001
printf("%05d %d -1\n",idx,w[idx]);
else
printf("%05d %d %05d\n",idx,w[idx],ne[idx]);
}
return 0;
}
不用vector
多一个pe数组 来存某一个结点的前驱的地址
#include<iostream>
using namespace std;
const int N=100010;
int ha,hb,n,idx;
int w[N],ne[N],pe[N];
int main(){
cin>>ha>>hb>>n;
for(int i=0;i<n;i++){
scanf("%d",&idx);
scanf("%d %d",&w[idx],&ne[idx]);
pe[ne[idx]]=idx;//下一个结点的前驱指向自己
}
//记录一个链表的长度 较长的那个一定大于等于n/3
int len=0;
for(int i=ha;~i;i=ne[i])len++;
if(len<n/2)swap(ha,hb);//保证ha 较长
pe[hb]=-1;//初始的前面设置为-1
while(ne[hb]!=-1)hb=ne[hb];//hb从后向前所以指向最后相当于反转
while(~hb){
//输出两个a结点 一个b结点
printf("%05d %d %05d\n",ha,w[ha],ne[ha]);
ha=ne[ha];
printf("%05d %d %05d\n",ha,w[ha],hb);
ha=ne[ha];
if(ha==-1)
printf("%05d %d -1\n",hb,w[hb]);
else
printf("%05d %d %05d\n",hb,w[hb],ha);
hb=pe[hb];
}
while(~ha){
if(ne[ha]==-1)
printf("%05d %d -1\n",ha,w[ha]);
else
printf("%05d %d %05d\n",ha,w[ha],ne[ha]);
ha=ne[ha];
}
return 0;
}