原题目：

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
结尾无空行

题解：

关键在于使用结构数组

这道题的情况很适合使用结构数组解决，二手信息如下：

此图截自于《The C Programming Language》中文译本P116。
于是有：

struct GNode{
    int data;
    int next;
}NodeTab[100000];

#include <stdio.h>

struct GNode{
    int data;
    int next;
}NodeTab[100000];
int main()
{
    int head,N,K;
    scanf("%d%d%d",&head,&N,&K);
    for(int i=0;i<N;i++){
        int address;
        scanf("%d",&address);
        scanf("%d%d",&NodeTab[address].data,&NodeTab[address].next);
    }
    //至此输入完成，链表储存完毕
    int p=head,cnt=0;
    while(p>=0){
        cnt++;
        p=NodeTab[p].next;
    }
    N=cnt;
    //这段代码是为了排除“有输入样例包含不在链表中的结点”的情况
    int k=N/K;
    int pre,PreHead;
    p=head;
    for(int j=0;j<k;j++){
        pre=p;
        p=NodeTab[p].next;
        int temp=pre;
        for(int i=1;i<K;i++){
            int temp=NodeTab[p].next;
            NodeTab[p].next=pre;//reverse
            pre=p;
            p=temp;//移向下一个结点
        }//此时p为下一组中第一个，pre为本组最后一个
        NodeTab[temp].next=p;
        if(j==0){
            head=pre;
        }else{
            NodeTab[PreHead].next=pre;
        }
        PreHead=temp;
    }
    //这段代码把N分成N/K组，对每组进行reverse，
    //并在相邻组之间通过PreHead、temp等变量实现连接
    p=head;
    while(p>=0){
        printf("%05d %d ",p,NodeTab[p].data);
        if(NodeTab[p].next==-1)
            printf("-1\n");
        else printf("%05d\n",NodeTab[p].next);
        p=NodeTab[p].next;
    }
    //这段代码是为了打印
    return 0;
}

结果：

心得：

这道题使用正确的数据结构之后，代码量只有不到50行，可见数据结构选择的重要性，学会更多种类的数据结构，就能在多种不同情况下得心应手。