PAT甲级A1074---反转链表

1074 Reversing Linked List (25分)

分析：

使用data[add]记录地址为add的数的值，next[add]记录add下一个结点的地址，list数组按顺序记录所有有效的结点地址，并用count记录一共有多少个有效结点。result数组记录最终反转之后的结果。

C++：

#include <cstdio>

using namespace std;

const int maxn = 100010;
int data[maxn], next[maxn], list[maxn], result[maxn];

int main() {
    int begin, n, k;
    scanf("%d%d%d", &begin, &n, &k);
    int add;
    for (int i = 0; i < n; i++) {
        scanf("%d", &add);
        scanf("%d%d", &data[add], &next[add]);
    }
    int count = 0;
    while (begin != -1) {
        list[count++] = begin;
        begin = next[begin];
    }
    for (int i = 0; i < count; i++) {
        result[i] = list[i];
    }
    //最后一组可能不反转，达到k个数才反转
    for (int i = 0; i < (count - count % k); i++) {
        //i/k*k为那一组第一个数，加上k-1是那一组最后一个数，再减去i%k就是与他反转的数
        result[i] = list[i / k * k + k - 1 - i % k];
    }
    for (int i = 0; i < count - 1; i++) {
        printf("%05d %d %05d\n", result[i], data[result[i]], result[i + 1]);
    }
    printf("%05d %d -1", result[count - 1], data[result[count - 1]]);
    return 0;
}