#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 11;

int head, e[maxn], ne[maxn], idx;

void init() {
    idx = 0;
    head = -1;
}

void insert_head(int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
}

void show(int head) {
    for(int i = head; i != -1; i = ne[i]) {
        cout << e[i] << " ";
    }
    cout << endl;
}

void reverse() {
    int cur = head;
    int pre = -1;

    while(cur != -1) {
        int nxt = ne[cur];
        ne[cur] = pre;
        pre = cur;
        cur = nxt;
    }

    head = pre;
}


void reverseK(int K) {
    // head的pre结点
    e[idx] = 0, ne[idx] = -1;
    int pre = idx;
    int cur = head;
    // 链表有idx个结点，需要迭代idx/K次
    for(int i = 0, j = idx/K; i < j; ++i) {
        int nxtPre = cur;
        for(int k = 0; k < K; ++k) {
            int nxt = ne[cur];
            ne[cur] = ne[pre];
            ne[pre] = cur;
            cur = nxt;
        }
        pre = nxtPre;
    }

    ne[pre] = cur;
    head = ne[idx];
}

int main() {
    init();
    // 头插法
    for(int i = 1; i <= 9; ++i) insert_head(i);
    show(head);
    // 整体反转
    reverse(); show(head);
    // K个一组翻转
    reverseK(2); show(head);

    return 0;
}