Source:PAT A1133 Splitting A Linked List (25 分）
Description: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 (≤) 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 Next
where Address is the position of the node, Data is an integer in [, 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
Keys:Attention:Code:错的 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，阈值K
12 接下来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_JUDGE
29 #else
30 freopen("Test.txt", "r", stdin);
31 #endif
32
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 else
51 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，阈值K
12 接下来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 node
27 {
28 int address,data,next;
29 }info[M];
30
31 int main()
32 {
33 #ifdef ONLINE_JUDGE
34 #else
35 freopen("Test.txt", "r", stdin);
36 #endif
37
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 else
54 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./content-4-264801.html
|
