L2-022 重排链表 (25 分)_l2-2 重排链表 分数 25 作者 陈越 单位 浙江大学 给定一个单链表 l 1 →l 2 →

给定一个单链表 L
​1→L2→⋯→Ln−1​​ →L​n，请编写程序将链表重新排列为 Ln​​ →L​1→L​n−1→L2 →⋯。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。

输入格式：

每个输入包含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
1
2
3
4
5
6
7

输出样例：

68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1
1
2
3
4
5
6

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
struct dot{
	int self,next;
	dot(){}
}peo[maxn],buf[maxn];
map<int,int>mp;
int root,n,u,cnt=0;
int main(){
	scanf("%d %d",&root,&n);
	for( int i=0; i<n; i++ ){
		scanf("%d",&u);
		scanf("%d %d",&peo[u].self,&peo[u].next);
		mp[peo[u].self]=u;
	}
	while(root!=-1){
		dot temp=peo[root];
		buf[cnt++]=temp;
		root=temp.next;
	}
	for( int i=0,j=cnt-1; i<=j; i++,j-- ){
		if(i==j) printf("%05d %d -1\n",mp[buf[j].self],buf[j].self);
		else{
			printf("%05d %d %05d\n",mp[buf[j].self],buf[j].self,mp[buf[i].self]);
			if(i==j-1) printf("%05d %d -1\n",mp[buf[i].self],buf[i].self);
			else printf("%05d %d %05d\n",mp[buf[i].self],buf[i].self,mp[buf[j-1].self]);
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31