PTA A_1074 Reversing Linked List

798236606

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

解：
链表+排序

#include<cstdio>
#include<algorithm>

using namespace std;

typedef struct Node{
    int add, data, next, key;
}node;

node a[100010];

bool cmp(node a, node b)
{
    return a.key < b.key;
}

int main(void)
{
    int head, n, k;
    
    scanf("%d %d %d", &head, &n, &k);
    
    for (int i = 0; i < n; i++)
    {
        int add;
        
        scanf("%d", &add);
        scanf("%d %d", &a[add].data, &a[add].next);
        a[add].add = add;
    }
    
    int count = 0, j = -n;
    for (int i = head; i != -1; i = a[i].next, count++)
        a[i].key = j++;

    sort(a, a + 100010, cmp);

    for (int i = 0; i < count / k; i++)
        reverse(a + i * k, a + (i + 1) * k);
        
    for (int i = 0; i < count - 1; i++)
        printf("%05d %d %05d\n", a[i].add, a[i].data, a[i + 1].add);
    
    printf("%05d %d -1", a[count - 1].add, a[count - 1].data);
    
    return 0;    
}