PAT A1133 Splitting A Linked List (25分)

前言

传送门

正文

参考题解

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
/* 题意： 拆分链表，将单链表中每个结点的data值按照负数，小于k,大于等于k进行排序， 保持原先链表上的顺序 思路：还是套模板，只是本题把节点分三类（-无穷，0）, [0,k], (k,+无穷) ,依次将它们 放到vector<Node> v容器中即可，最后输出 注意： */
const int N=1e5+10;
//第一步 
struct Node{
	int addr,data,next;
	int order;
}node[N];
//排序的目的就是将合法结点和非法结点分开 
bool cmp(Node a,Node b){
	return a.order<b.order;
} 
int main(){
	//第二步 
	for(int i=0;i<N;i++)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,N};
	}
	//第三步
	int p=head,cnt=0;
	while(p!=-1){
		node[p].order=cnt++;
		p=node[p].next;
	} 
	//第四步
	sort(node,node+N,cmp);
	//第五步
	//分三类加入到vector中 
	vector<Node> v;
	for(int i=0;i<cnt;i++){
		if(node[i].data<0)v.push_back(node[i]);
	}
	for(int i=0;i<cnt;i++){
		if(node[i].data>=0&&node[i].data<=k)v.push_back(node[i]);
	}
	for(int i=0;i<cnt;i++){
		if(node[i].data>k)v.push_back(node[i]);
	}
	for(int i=0;i<cnt;i++){
		if(i!=cnt-1)printf("%05d %d %05d\n",v[i].addr,v[i].data,v[i+1].addr);
		else printf("%05d %d -1\n",v[i].addr,v[i].data);
	} 
	return 0;
}