AcWing 1560. 反转链表
原题链接
中等
作者:
Richard_4
,
2021-05-10 15:23:34
,
所有人可见
,
阅读 299
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
int e[N],ne[N];
int reverse(int head,int k){ //从head的下一个结点开始反转
int tail=ne[head]; //反转之后的尾结点,最终需要返回,以便对接下来的链表进行反转
int pL=ne[head];
int pR=ne[pL];
for(int i=0;i<k-1;i++){ //k个结点需要反转k-1次
int t=ne[pR];
ne[pR]=pL;
pL=pR;
pR=t;
}
ne[head]=pL; //把反转之后的子链表和整个链表链接起来
ne[tail]=pR;
return tail;
}
int main(){
int head,n,k;
scanf("%d%d%d",&head,&n,&k);
int vir_head=N-1; //因为reverse函数是从head的下一个结点开始反转,因此需要创建一个虚拟的头节点(y总之前的方法不需要头节点,在其基础上略作改动)
ne[vir_head]=head;
int add,data,next;
for(int i=0;i<n;i++){ //读入数据
scanf("%d%d%d",&add,&data,&next);
e[add]=data;
ne[add]=next;
}
//统计链表的有效长度
int cnt=0;
for(int i=head;i!=-1;i=ne[i]){
cnt++;
}
// printf("cnt=%d\n",cnt);
int p=vir_head;
for(int i=0;i+k<=cnt;i+=k){
p=reverse(p,k);
}
if(cnt==0) printf("-1\n");
else{
for(int i=ne[vir_head];i!=-1;i=ne[i]){
if(ne[i]!=-1){
printf("%05d %d %05d\n",i,e[i],ne[i]);
}
else{
printf("%05d %d %d\n",i,e[i],ne[i]);
}
}
}
return 0;
}