A30293. 重链重排
填空题
困难
知识点
题目描述
重链重排
题目描述
给定一个单链表 L1 →L2 →…→Ln-1 →Ln ，请编写程序将链表重新排列为Ln →L1 →Ln-1 →L2 →…。例如： 给定 L 为 1 →2→3→4→5→6，则输出应该为6→1 →5→2→4→3。
时间限制： 1000 内存限制： 65536
输入
每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址和结点总个数，即正整数 N (≤ 105)。结点的地址是 5 位非负整数，NULL 地址用-1 表示。
接下来有 N行，每行格式为： Address Data Next 其中`Address`是结点地址；
`Data`是该结点保存的数据，为不超过 105 的正整数； `Next`是下一结点的地址。
题目保证给出的链表上至少有两个结点。
输出
对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。
样例输入
00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
样例输出
68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1
参考答案
#include<cstdio>
using namespace std;
struct node{
int a,n;
}f[200000];
int ad,n,i,j,l,r,ll[200000],a,b,h[200000],c,k,k1;
int main()
{
while (~scanf("%d%d",&ad,&n))
{
for (i=1; i<=n; i++)
{
scanf("%d%d%d",&a,&b,&c);
f[a].a=b;
f[a].n=c;
}
k=0;
while (ad>=0)
{
h[k++]=ad;
ad=f[ad].n;
}
l=0;
r=k-1;
k1=0;
while (l<=r)
{
if (l==r)
{
ll[k1++]=h[r--];
}
else
{
ll[k1++]=h[r--];
ll[k1++]=h[l++];
}
}
for (i=0; i<k1-1; i++)
{
printf("%05d %d %05d\n",ll[i],f[ll[i]].a,ll[i+1]);
}
printf("%05d %d -1\n", ll[k1-1],f[ll[k1-1]].a);
}
}
上一题
下一题