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; }