1133 Splitting A Linked List (25分) 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.
Input Specification: 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.
Output Specification: 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.
Sample 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 Sample Output: 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 此题题意理解错直接扑该，原意将链表的数据按照数据的大小分成三段，而不是以10为分界进行分割。 通过不断地调试渐渐掌握几种方法，都是在实在误解题意的情况下悟到的，其中直接对cmp函数进行运算最为简单。 代码：
#include<iostream> #include<algorithm> int k; using namespace std; struct Node{ int address,key,next,order; bool flag; }node[100000]; int cmp(Node a,Node b){ if(a.flag==false||b.flag==false) return a.flag>b.flag; else if(a.key<0&&b.key<0) return a.order<b.order; else if(a.key>=0&&a.key<=k&&b.key>=0&&b.key<=k) return a.order<b.order; else if(a.key>k&&b.key>k) return a.order<b.order; else return a.key<b.key; } int main(){ int a,b; scanf("%05d%d%d",&a,&b,&k); for(int i=0;i<100000;i++){ node[i].order=100000; } for(int i=0;i<b;i++){ int d,e,f; scanf("%05d%d%05d",&d,&e,&f); node[d].address=d; node[d].flag=false; node[d].key=e; node[d].next=f; } int cnt=0; for(int i=a;i!=-1;i=node[i].next){ node[i].flag=true; node[i].order=cnt++; } sort(node,node+100000,cmp); for(int i=0;i<cnt;i++){ if(i!=cnt-1) printf("%05d %d %05d\n",node[i].address,node[i].key,node[i+1].address); else printf("%05d %d -1\n",node[i].address,node[i].key); } }当然还可以常规思路：
#include<iostream> #include<algorithm using namespace std; struct Node{ int address,key,next,order; bool flag; }node[100000]; int cmp(Node a,Node b){ if(a.flag==false||b.flag==false) return a.flag>b.flag; else return a.order<b.order; } int main(){ int a,b; scanf("%05d%d%d",&a,&b,&k); if(b==0){ return 0; } for(int i=0;i<100000;i++){ node[i].order=100000; } for(int i=0;i<b;i++){ int d,e,f; scanf("%05d%d%05d",&d,&e,&f); node[d].address=d; node[d].flag=false; node[d].key=e; node[d].next=f; } int cnt=0; for(int i=a;i!=-1;i=node[i].next){ node[i].flag=true; node[i].order=cnt++; } sort(node,node+100000,cmp); int s=0; for(int i=0;i<cnt;i++){ if(node[i].key<0){ node[i].order=s++; } } for(int i=0;i<cnt;i++){ if(node[i].key<=k&&node[i].key>=0){ node[i].order=++s; } } for(int i=0;i<cnt;i++){ if(node[i].key>k) node[i].order=++s; } sort(node,node+cnt,cmp); for(int i=0;i<cnt;i++){ if(i!=cnt-1) printf("%05d %d %05d\n",node[i].address,node[i].key,node[i+1].address); else printf("%05d %d -1\n",node[i].address,node[i].key); } }