Given a singly linked list, you are supposed to rearrange its elements so that all the negative values appear before all of the non-negatives, and all the values in [0, K] appear before all those greater than K. The order of the elements inside each class must not be changed. For example, given the list being 18→7→-4→0→5→-6→10→11→-2 and K being 10, you must output -4→-6→-2→7→0→5→10→18→11.
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤10?5??) which is the total number of nodes, and a positive K (≤10?3??). The address of a node is a 5-digit nonnegative integer, and NULL is represented by ?1.
Then N lines follow, each describes a node in the format:
Address Data Next
where Address is the position of the node, Data is an integer in [?10?5??,10?5??], and Next is the position of the next node. It is guaranteed that the list is not empty.
For each case, output in order (from beginning to the end of the list) the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.
00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218
33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1
1 #include <stdio.h> 2 #include <string> 3 #include <iostream> 4 #include <algorithm> 5 #include <vector> 6 using namespace std; 7 const int maxn=100010; 8 struct node{ 9 int data; 10 int pos=0; 11 int address; 12 int next; 13 int rank; 14 }nodes[maxn]; 15 vector<node> v; 16 int n,k,root; 17 bool cmp(node n1,node n2){ 18 if(n1.rank<n2.rank) return true; 19 else if(n1.rank>n2.rank) return false; 20 else{ 21 return n1.pos<n2.pos; 22 } 23 } 24 int main(){ 25 scanf("%d %d %d",&root,&n,&k); 26 for(int i=0;i<n;i++){ 27 int first,data,next; 28 scanf("%d %d %d",&first,&data,&next); 29 node tmp; 30 tmp.address = first; 31 tmp.data = data; 32 tmp.next = next; 33 if(data<0) tmp.rank=1; 34 else if(data<=k) tmp.rank=2; 35 else tmp.rank=3; 36 nodes[first]=tmp; 37 //v.push_back(tmp); 38 } 39 int j=1; 40 while(root!=-1){ 41 nodes[root].pos=j; 42 v.push_back(nodes[root]); 43 root=nodes[root].next; 44 j++; 45 } 46 sort(v.begin(),v.end(),cmp); 47 for(int i=0;i<v.size();i++){ 48 if(i!=v.size()-1){ 49 printf("%05d %d %05d\n",v[i].address,v[i].data,v[i+1].address); 50 } 51 else { 52 printf("%05d %d -1\n",v[i].address,v[i].data); 53 } 54 } 55 }
注意点：看到只想着排序了，看大佬的方法真简单，直接三个vector，再合起来打印输出。
一开始最后第二个测试点，最后一个超时，超时是因为一开始存数据直接存在vector里，然后要得到正确的顺序每次都要遍历一遍整个vector，时间复杂度很高。而且最开始的pos其实设置的也是有问题的，直接根据输入顺序得到了，神奇的是结果居然前几个都是对的。
最后存储链表还是要用静态数组，不能用vector，找next太耗时
PAT A1133 Splitting A Linked List （25 分）
原文：https://www.cnblogs.com/tccbj/p/10423894.html
