PAT甲级真题1074
思路来源

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;

int e[N], ne[N];
//反转链表函数
/*
    head为区间前部外面的结点，ne[head]指向要翻转的区间的第一个链表结点。
    rear记录区间内的第一个结点，也就是反转后的最后一个结点
    PL 和 PR 是一个滚动序列，区间内部如果有k个结点，那么就要翻转k-1次，翻转前k-1个结点，PL指向前结点，PR指向后结点
    翻转完前k-1个结点之后，PL指向区间内的最后一个结点，PR指向区间外的下一个序列的第一个结点，rear现在来到了最后面，ne[rear] = PR, PL是区间内的第一个结点，ne[head] = PL;
    然后在返回当前区间的最后一个结点，也就是rear，用来做下一次翻转操作的head

*/
int reverse(int head, int k) {      
    int rear = ne[head];
    int PL = ne[head];
    int PR = ne[PL];
    for (int i = 0; i < k - 1; i ++) {      
        int t = ne[PR];
        ne[PR] = PL;

        PL = PR;
        PR = t;
    }
    ne[head] = PL;
    ne[rear] = PR;

    return rear;
}

int main() {
    int head = N - 1;
    int h, n, k;
    cin >> h >> n >> k;
    ne[head] = h;
    int addr, data, nextAddr;
    for (int i = 0; i < n; i ++) {
        cin >> addr >> data >> nextAddr;
        e[addr] = data;
        ne[addr] = nextAddr;
    }

    //记录结点的个数
    int cnt = 0;
    for (int i = ne[head]; i != -1; i = ne[i]) cnt ++;      //记录一条链表中有多少结点，排除其他的不在链表上的结点
    n = cnt;        

    //反转链表
    int p = head;
    for (int i = 0; i + k <= n; i += k) p = reverse(p, k);  //i + k 是下一个翻转区间的第一个结点，等号成立时表明n可以被k整除，恰好可以翻转整个链表

    //打印链表
    for (int i = ne[head]; i != -1; i = ne[i]) {
        printf("%05d %d ", i, e[i]);
        if (ne[i] != -1) 
            printf("%05d\n", ne[i]);
        else 
            printf("-1\n");
    }


    return 0;
}

stl版

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;

int e[N], ne[N], link[N];
int main() {
    int head = N - 1;
    int h, n, k;
    cin >> h >> n >> k;
    ne[head] = h;
    int addr, data, nextAddr;   //使用一个link数组存储address，利用stl中的reverse函数翻转
    for (int i = 0; i < n; i ++) {
        cin >> addr >> data >> nextAddr;
        e[addr] = data;
        ne[addr] = nextAddr;
    }
    int cnt = 0;
    for (int i = ne[head]; i != -1; i = ne[i]) {
        link[cnt ++] = i;
    } 
    n = cnt;
    int p = head;
    for (int i = 0; i + k <= n; i += k) reverse(link + i, link + i + k);
    for (int i = 0; i < n; i ++) {
        if (i < n - 1)
            printf("%05d %d %05d\n", link[i], e[link[i]], link[i + 1]);
        else
            printf("%05d %d -1\n", link[i], e[link[i]]);
    }


    return 0;
}