STL,模拟链表
$O(n)$
将链表模拟成数组,然后再以链表的形式输出
这里取最方便的vector进行存储
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=100010;
int e[N],ne[N];
int idx=0;
int main()
{
int h1,h2,n; cin>>h1>>h2>>n;
while(n--)
{
int a,b,c; cin>>a>>b>>c;
e[a]=b,ne[a]=c;
}
vector<int> a,b,res;
for(int i=h1;~i;i=ne[i]) a.push_back(i);
for(int i=h2;~i;i=ne[i]) b.push_back(i);
if(a.size()<b.size()) swap(a,b);
reverse(b.begin(),b.end());
for(int i=0,j=0;i<a.size();i++)
{
res.push_back(a[i]);
if((i+1)%2==0&&j<b.size()) res.push_back(b[j++]);
}
for(int i=0;i<res.size();i++)
{
printf("%05d %d ",res[i],e[res[i]]);
if(i==res.size()-1) cout<<-1<<endl;
else printf("%05d\n",res[i+1]);
}
return 0;
}