线性结构3 Reversing Linked List (25 分)

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，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

code

/*算法： 1.对输入对address，data，next进行存储 下面用到是结构体数组，node[address]，下标为address，结构体变量data,next 2.将反转链表简化为反转数组 再创建一个list数组对address按照顺序存储，对K个数内部进行反转 3.根据反转后对数组，找到关联对data,next进行输出 */

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100002

 struct Node {
    int Data;
    int Next;
};

int main()
{
    struct Node node[MAXSIZE];
    int list[MAXSIZE];
    int frist,n,k,temp;
    scanf("%d %d %d",&frist,&n,&k);
    int address,data,next;

    /*输入到结构体数组存储*/
    for(int i=0;i<n;i++)
    {
        scanf("%d %d %d",&address,&data,&next);
        node[address].Data = data;
        node[address].Next = next;
// printf("node[%05d].Data=%d,node[%05d].Next=%05d\n",address,node[address].Data,address,node[address].Next);
    }

    /*对address进行按序存储 remark：这里要注意输入对结点中可能有有多余结点不在链表上，即存在（cnt<n）, */
    address = frist;
    int cnt = 0;
    while(address != -1)
    {
        list[cnt] = address;
        address = node[address].Next;
// printf("list[%d]=%05d\n",j,list[j]);
        cnt++;
    }
	
	/*反转数组*/
    for(int i=0;i<=cnt-k;i+=k)
    {
        for(int h=0;h<k/2;h++)
        {
            temp = list[i+h];
            list[i+h] = list[i-h+k-1];
            list[i-h+k-1] = temp;
// printf("list[%d+%d]=%05d,list[%d-%d+k-1]=%05d\n",i,h,i,h,list[i+h],list[i-h+k-1]);
        }
    }
	/*输出*/
    for(int i=0;i<cnt-1;i++)
    {
        printf("%05d %d %05d\n",list[i],node[list[i]].Data,list[i+1]);

    }
    printf("%05d %d -1\n",list[cnt-1],node[list[cnt-1]].Data);
    return 0;
}