A1074. Reversing Linked List

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K = 3, then you must output 3→2→1→6→5→4; if K = 4, you must output 4→3→2→1→5→6.

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⁵) which is the total number of nodes, and a positive K (<=N) which is the length of the sublist to be reversed. 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, and Next is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

Sample Output:

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef struct NODE{
 6     int lt, rt;
 7     int valid;
 8     int data, rk;
 9 }node;
10 node nds[100001];
11 bool cmp(node a, node b){
12     if(a.valid != b.valid)
13         return a.valid > b.valid;
14     else return a.rk < b.rk;
15 }
16 bool cmp2(node a, node b){
17     return a.rk > b.rk;
18 }
19 int main(){
20     int N, K, head;
21     scanf("%d%d%d", &head, &N, &K);
22     int temp;
23     for(int i = 0; i < N; i++){
24         scanf("%d", &temp);
25         nds[temp].lt = temp;
26         scanf("%d%d", &nds[temp].data, &nds[temp].rt);
27     }
28     int pt = head, cnt = 0;
29     while(pt != -1){
30         nds[pt].valid = 1;
31         nds[pt].rk = cnt;  
32         cnt++;
33         pt = nds[pt].rt;
34     }
35     sort(nds, nds + 100001, cmp);
36     for(int i = 0; i + K <= cnt; i += K){
37         sort(nds + i, nds + i + K, cmp2);
38     }
39     if(cnt == 0)
40         printf("-1");
41     for(int i = 0; i < cnt; i++){
42         if(i < cnt - 1)
43             printf("%05d %d %05d
", nds[i].lt, nds[i].data, nds[i + 1].lt);
44         else printf("%05d %d -1
", nds[i].lt, nds[i].data);
45     }
46     cin >> N;
47     return 0;
48 }

View Code

总结：

1、注意链表节点的初始顺序不是读入的顺序，而是在读完之后，从给定的首地址遍历一遍的顺序。

2、静态链表题一般都会在输入中放入无效节点，需要过滤掉。注意全空的情况。

3、本题可以在第一次遍历合法节点的时候，给每个节点都编号0、1、2......，然后按照valid和节点编号排序，这样可以将所有节点聚集起来且按照链表本身的顺序依次存放。之后第二遍遍历，每K个从大到小再排一次序即可得到最终的顺序。

4、每个节点自己的地址是始终不变的。

5、只有到了最后一步才可以把所有合法节点聚集到数组前部。

6、测试点

　　00000 6 3
　　00000 1 11111
　　11111 2 22222
　　22222 3 -1
　　33333 4 44444
　　44444 5 55555
　　55555 6 -1