Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤10
​5
​​ ) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

Sample Output:

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

思路:

先用数组模拟连续的内存地址来存储结点。链表每k个元素反转可以分解为两个函数：第一个函数接收前一部分的尾地址和反转部分的链表的起始地址和反转的元素个数进行反转并将前一部分和反转部分连接，返回反转后的起始地址和结束地址和下一部分的首地址（反转后会和下一部分断连），第二个函数作为主调函数，传入要反转的参数，并将返回的指针重新连接，如果剩余元素个数不足则不进行反转而是直接连接。
可能讲得很乱（因为我也没有搞懂）

代码:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

int start, n, step;
typedef struct
{
    int data;
    int next;
} Node, *List;

List input()
{
    int addr, data, next;
    List L = new Node[100010];
    std::cin >> start >> n >> step;
    for (int i = 0; i < n; ++i)
    {
        std::cin >> addr >> data >> next;
        L[addr].data = data;
        L[addr].next = next;
    }
    return L;
}

int reverse(List L, int head, int k, int pre, int &next)
{
    int cur_addr = head, prior_addr = -1, next_addr;
    for (int i = 0; i < k; i++)
    {
        next_addr = L[cur_addr].next;
        L[cur_addr].next = prior_addr;
        prior_addr = cur_addr;
        cur_addr = next_addr;
    }
    if (pre != -1)
    {
        L[pre].next = prior_addr;
    }
    next = cur_addr;
    return prior_addr;
}

void change(List L)
{
    int head = start, rear, pre = -1, next;
    for (int i = 0; i < n; ++i)
    {
        head = L[head].next;
        if (head == -1)
        {
            n = i + 1;
            break;
        }
    }
    head = start;
    for (int i = 1; i * step <= n; ++i)
    {
        rear = head;
        head = reverse(L, head, step, pre, next);
        pre = rear;
        if (start == rear)
            start = head;
        if ((i + 1) * step > n)
            L[rear].next = next;
        head = next;
    }
}

void output(List L)
{
    int addr = start;
    for (int i = 0; i < n; ++i)
    {
        printf("%05d %d ", addr, L[addr].data);
        addr = L[addr].next;
        if (addr == -1)
        {
            printf("-1\n");
            break;
        }
        else
            printf("%05d\n", addr);
    }
}

int main()
{
    List list = input();
    change(list);
    output(list);
    return 0;
}