1074 Reversing Linked List (25 分)

Reversing Linked List

版本1

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct node{
	int add,value,index,next;
}E[maxn];
bool cmp(node a, node b){
	return a.index < b.index;

}
bool cmp1(node a, node b){
	return a.index > b.index;
}

int main(){
	int p,n,add,value,next,t=0,k;
	cin>>p>>n>>k;
	for(int i=0;i<maxn;i++){
		E[i].index = maxn;
	}
	for(int i=0;i<n;i++){
		cin>>add>>value>>next;
		E[add].add = add;
		E[add].value = value;
		E[add].next = next;
	}
	
	while(p!=-1){
		E[p].index=t;
		p = E[p].next;
		t++; 
	}
	sort(E,E+maxn,cmp); 
	//隔K步反转 
	for(int i=0;i<=t-k;i+=k){ //这个等号很关键 
		sort(E+i, E+i+k,cmp1);
	}
	//输出 
	for(int i=0;i<t;i++){
		printf("%05d %d",E[i].add,E[i].value);
		if(i!=t-1) printf(" %05d\n",E[i+1].add);
		else printf(" -1\n");
	}
	return 0;
}