前言

传送门

正文

#include<iostream>
#include<algorithm>
using namespace std;
/* 题意：翻转单链表 每间隔k进行链表翻转 思路：套用静态链表模板解题步骤，参照PAT A1052 注意：本题需要按照每k个结点分块，若最后一个块结点数不足k个（不完整的块） 则最后这个块不需要翻转。 而对于非最后一个块的其他块则需要翻转，同时需要 注意翻转后的这个块的最后一个结点的next需要指向下一个块的第一个结点/最后一个结点 （需要看这个"下一个块"是否是不完整的块） */
const int N=1e5+10;
//步骤一：定义结构体数组 
struct Node{
	int addr,data,next;
	bool flag;//是否是链表中的结点 
	int order;//链表中的结点的下标（用于排序） 
}node[N];
bool cmp(Node a,Node b){
	if(!a.flag||!b.flag) return a.flag>b.flag;
	else return a.order<b.order;//都是有效结点则按照在链表中出现的顺序排序 
} 
int main(){
	//步骤二：初始化 
	for(int i=0;i<N;i++){
		node[i].flag=false;
		node[i].order=N;
	}
	int head,n,k;
	cin>>head>>n>>k;
	int addr,data,next;
	//读入 
	for(int i=0;i<n;i++){
		cin>>addr>>data>>next;
		node[addr]={addr,data,next};
	} 
	//步骤三：枚举链表
	int p=head,cnt=0;//cnt表示链表中的结点个数
	while(p!=-1){
		node[p].flag=true;
		node[p].order=cnt++;
		p=node[p].next;
	} 
	//步骤四：排序 
	sort(node,node+N,cmp);
	
	//步骤五：根据题意输出 
	for(int i=0;i<cnt/k;i++){//首先枚举完整的n/k块，每一块都有k个结点 
		for(int j=(i+1)*k-1;j>i*k;j--){
			//从后往前遍历每一个完整块中的每一个结点，除去第一个结点（j>i*k而非大于等于），
			//因为这个结点的next要视情况判断时是下一个完整块还是不完整块 
			printf("%05d %d %05d\n",node[j].addr,node[j].data,node[j-1].addr); 
		} 
		printf("%05d %d ",node[i*k].addr,node[i*k].data);
		if(i<cnt/k-1){//若本块不是最后一个完整块，那么需要指向下一个完整块的最后一个结点 
			printf("%05d\n",node[(i+2)*k-1].addr);
		}else{//本块是最后一个完整块 
			if((i+1)*k==cnt){//恰好没有不完整块 
				printf("-1\n"); 
			}else{
				printf("%05d\n",node[(i+1)*k].addr); 
				//输出不完整块（需要按照原先的顺序输出） 
				for(int i=cnt/k*k;i<cnt;i++){
					printf("%05d %d ",node[i].addr,node[i].data);
					if(i<cnt-1)printf("%05d\n",node[i+1].addr);
					else printf("-1\n");
				} 
			}
		}
	}
	return 0;
}