problem
L2-022 重排链表 (25分) 给定一个单链表 L 1 →L 2 →⋯→L n−1 →L n ，请编写程序将链表重新排列为 L n →L 1 →L n−1 →L 2 →⋯。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。
输入格式： 每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N (≤10 5 )。结点的地址是5位非负整数，NULL地址用−1表示。
接下来有N行，每行格式为：
Address Data Next 其中Address是结点地址；Data是该结点保存的数据，为不超过10 5 的正整数；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
solution
题意：给出链表L为1→2→3→4→5→6，将其重排为6→1→5→2→4→3并输出。把原始链表数据先存下来，然后再按顺序遍历一遍即可。样例4有毒，可能存在不在链表上的点，所以输入后还得自己跑一遍链表长度。
#include<bits/stdc++.h>
using namespace std
;
const int maxn
= 100010;
struct node
{ int address
, data
, next
;}li
[maxn
];
vector
<node
>l1
, l2
;
int main(){
int begin
, n
;
cin
>>begin
>>n
;
for(int i
= 1; i
<= n
; i
++){
int x
; cin
>>x
; li
[x
].address
= x
;
cin
>>li
[x
].data
>>li
[x
].next
;
}
int mid
= n
/2, cnt
= 0;
for(int i
= begin
; i
!= -1; i
=li
[i
].next
)cnt
++;
mid
= cnt
/2, cnt
= 0;
for(int i
= begin
; i
!= -1; i
=li
[i
].next
){
cnt
++;
if(cnt
<=mid
){
l1
.push_back(li
[i
]);
}else{
l2
.push_back(li
[i
]);
}
}
for(int i
=0,j
=l2
.size()-1; i
<l1
.size() && j
>=0; i
++,j
--){
printf("d %d ", l2
[j
].address
,l2
[j
].data
);
printf("d\n", l1
[i
].address
);
printf("d %d ", l1
[i
].address
,l1
[i
].data
);
if(j
!=0)printf("d\n", l2
[j
-1].address
);
else printf("-1\n");
}
if(cnt
%2==1){
printf("d %d ",l2
[0].address
,l2
[0].data
);
printf("-1\n");
}
return 0;
}
