PTA A_1074 Reversing Linked List

798236606

传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805394512134144

解：
链表+排序

1. #include<cstdio>
   
2. #include<algorithm>
   
3. 
   
4. using namespace std;
   
5. 
   
6. typedef struct Node{
   
7.     int add, data, next, key;
   
8. }node;
   
9. 
   
10. node a[100010];
    
11. 
    
12. bool cmp(node a, node b)
    
13. {
    
14.     return a.key < b.key;
    
15. }
    
16. 
    
17. int main(void)
    
18. {
    
19.     int head, n, k;
    
20.    
    
21.     scanf("%d %d %d", &head, &n, &k);
    
22.    
    
23.     for (int i = 0; i < n; i++)
    
24.     {
    
25.         int add;
    
26.         
    
27.         scanf("%d", &add);
    
28.         scanf("%d %d", &a[add].data, &a[add].next);
    
29.         a[add].add = add;
    
30.     }
    
31.    
    
32.     int count = 0, j = -n;
    
33.     for (int i = head; i != -1; i = a[i].next, count++)
    
34.         a[i].key = j++;
    
35. 
    
36.     sort(a, a + 100010, cmp);
    
37. 
    
38.     for (int i = 0; i < count / k; i++)
    
39.         reverse(a + i * k, a + (i + 1) * k);
    
40.         
    
41.     for (int i = 0; i < count - 1; i++)
    
42.         printf("%05d %d %05d\n", a[i].add, a[i].data, a[i + 1].add);
    
43.    
    
44.     printf("%05d %d -1", a[count - 1].add, a[count - 1].data);
    
45.    
    
46.     return 0;   
    
47. }

复制代码