前言

传送门

正文


参考题解

#include<iostream>
#include<algorithm>

using namespace std;

/* 题意： 静态链表排序，按照链表上结点的data值排序输出 思路：按照算法笔记的模板做即可。 模板总的来说就五步（必备）： 1、定义静态链表（需要注意根据题意灵活添加成员变量如flag,order,addr） order在需要记录每个结点在链表中的编号时添加，addr在需要排序时添加，因为 排序会使得不再以下标作为地址。 2、初始化（主要是将flag初始化，因为不一定所有给出的结点都是在链表上的） 3、枚举链表，对flag进行标记，同时计数有效结点个数 4、根据题意筛选有效结点，一般就是排序（注意排序比较函数cmp） 5、按照输出格式进行输出 注意：根据不同题目的条件需要在node结构体中添加不同成员变量， 比如flag表示该结点是否在链表上，还有realCnt表示链表上实际的 结点数。 本题需要注意特判realCnt==0的情况。同时需要注意排序后 的结点node[i]的next就不是node[i].next了，而是node[i+1].addr。 */

const int N=1e5+10;
//定义结构体 
struct Node{
	int addr,data,next;
	bool flag; 
}node[N];
//排序函数 
bool cmp(Node a,Node b){
	if(!a.flag||!b.flag)return a.flag>b.flag;
	else return a.data<b.data;
}
int main(){
	int n,head;
	cin>>n>>head;
	//初始化 
	for(int i=0;i<N;i++)node[i].flag=false;
	int addr,data,next;
	while(n--){
		cin>>addr>>data>>next;
		node[addr]={addr,data,next,false};
	}
	int realCnt=0,p=head;
	while(p!=-1){
		realCnt++;//记录实际结点数 
		node[p].flag=true;
		p=node[p].next;
	}
	if(realCnt==0)printf("0 -1\n");
	else{
		sort(node,node+N,cmp);//按照题意排序
		printf("%d %05d\n",realCnt,node[0].addr);
		for(int i=0;i<realCnt;i++){
			if(i!=realCnt-1) printf("%05d %d %05d\n",node[i].addr,node[i].data,node[i+1].addr);
			else printf("%05d %d -1\n",node[i].addr,node[i].data);
		} 
	} 
	return 0;
}