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 (≤) which is the total number of nodes, and a positive K (≤). The address of a node is a 5-digit nonnegative integer, and NULL is represented by −.
Then N lines follow, each describes a node in the format:
Address Data Nextwhere
Addressis the position of the node,Datais an integer in [, andNextis 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 1023333 10 2777700000 0 9999900100 18 1230968237 -6 2333333218 -4 0000048652 -2 -199999 5 6823727777 11 4865212309 7 33218
33218 -4 6823768237 -6 4865248652 -2 1230912309 7 0000000000 0 9999999999 5 2333323333 10 0010000100 18 2777727777 11 -1
链表
散列（Hash）
题目不难，但是用map最后一个测试点过不去，换结构体存储就可以了，搞不懂0,0
【错误代码】放这里，向各位大佬请教，十分感激。
1 /* 2 Data: 2019-06-24 16:20:53 3 Problem: PAT_A1133#Splitting A Linked List 4 AC: 5 6 题目大意： 7 重排单链表，不改变原先顺序的前提下，使得 8 1.负数在前，正数在后； 9 2.正数中，小于K元素在前，大于K的在后；10 输入：11 第一行给出，首元素地址，结点数N<=1e5，阈值K12 接下来N行，地址，数值，下一个地址13 输出：14 地址，数值，下一个地址15 16 基本思路：17 建立数值->地址，地址->数值，地址->下个地址的映射18 按顺序存储链表中有效的数值，再按要求排序，输出；19 */20 21 #include<cstdio>22 #include<map>23 #include<vector>24 using namespace std;25 26 int main()27 {28 #ifdef ONLINE_JUDGE29 #else30 freopen("Test.txt", "r", stdin);31 #endif32 33 int first,n,k,address,data,next;34 vector<int> link,L1,L2;35 map<int,int> adr,key,nex;36 scanf("%d%d%d", &first,&n,&k);37 for(int i=0; i<n; i )38 {39 scanf("%d%d%d", &address,&data,&next);40 adr[data] = address;41 key[address] = data;42 nex[address] = next;43 }44 while(first != -1)45 {46 if(key[first] < 0)47 link.push_back(key[first]);48 else if(key[first] <= k)49 L1.push_back(key[first]);50 else51 L2.push_back(key[first]);52 first = nex[first];53 }54 link.insert(link.end(),L1.begin(),L1.end());55 link.insert(link.end(),L2.begin(),L2.end());56 57 for(int i=0; i<link.size(); i )58 {59 if(i != 0)60 printf("d\n", adr[link[i]]);61 printf("d %d ", adr[link[i]], link[i]);62 }63 printf("-1\n");64 65 return 0;66 } 1 /* 2 Data: 2019-06-24 16:20:53 3 Problem: PAT_A1133#Splitting A Linked List 4 AC: 58:37 5 6 题目大意： 7 重排单链表，不改变原先顺序的前提下，使得 8 1.负数在前，正数在后； 9 2.正数中，小于K元素在前，大于K的在后；10 输入：11 第一行给出，首元素地址，结点数N<=1e5，阈值K12 接下来N行，地址，数值，下一个地址13 输出：14 地址，数值，下一个地址15 16 基本思路：17 结构体存储链表信息18 按顺序存储链表中有效的数值，再按要求排序，输出；19 */20 21 #include<cstdio>22 #include<map>23 #include<vector>24 using namespace std;25 const int M=1e6 10;26 struct node27 {28 int address,data,next;29 }info[M];30 31 int main()32 {33 #ifdef ONLINE_JUDGE34 #else35 freopen("Test.txt", "r", stdin);36 #endif37 38 int first,n,k,adr;39 vector<node> link,L1,L2;40 scanf("%d%d%d", &first,&n,&k);41 for(int i=0; i<n; i )42 {43 scanf("%d", &adr);44 info[adr].address=adr;45 scanf("%d%d", &info[adr].data,&info[adr].next);46 }47 while(first != -1)48 {49 if(info[first].data < 0)50 link.push_back(info[first]);51 else if(info[first].data <= k)52 L1.push_back(info[first]);53 else54 L2.push_back(info[first]);55 first = info[first].next;56 }57 link.insert(link.end(),L1.begin(),L1.end());58 link.insert(link.end(),L2.begin(),L2.end());59 60 for(int i=0; i<link.size(); i )61 {62 if(i != 0)63 printf("d\n", link[i].address);64 printf("d %d ", link[i].address, link[i].data);65 }66 printf("-1\n");67 68 return 0;69 }来源：https://www.icode9.com/content-4-264801.html
联系客服
