A1074

1074 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 (≤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


#include<stdio.h>
struct node{
int data;   //数据
int next;   //下一个结点的地址
}p[100005];
int main(){
    int N,K,first,ad;
    int lb=0,l=0,i;

    int b[100005],ans[100005];
    scanf("%d %d %d",&first,&N,&K); 
    for(i=0;i<N;i++){
        scanf("%d",&ad);
        scanf("%d %d",&p[ad].data,&p[ad].next); 
    }
    while(first!=-1){//给链表正常排序 （这个步骤在排序的过程中，也把输入中的垃圾结点过滤掉了（输入的结点不一定在链表上））
        b[lb]=first;
        first=p[first].next;    //地址作为下标后，通过地址就可以找到下一个结点的地址了
        lb++;
    }
    int y=lb%K; // y是余数，最后存 
    for(i=0;i<lb-y;i++){
        if((i+1)%K==0){  //如果满足K个，就将反转 
            for(int j=i;j>=i+1-K;j--){ 
                ans[l]=b[j];l++;
            }
        }
    }
    if(y){  //如果余数不为0，最后部分正序补上 
        for(i=lb-y;i<lb;i++){
            ans[l]=b[i];l++;
        }
    }
    for(i=0;i<l;i++){   //输出的格式是address  data  next
        if(i!=l-1)printf("%05d %d %05d\n",ans[i],p[ans[i]].data,ans[i+1]);     //这里ans[i]为当前结点的地址 p[ans[i]].data就是地址指向的结点的数据 ans[i+1]为下一个地址 
        else printf("%05d %d -1\n",ans[i],p[ans[i]].data);  //因为最后一个结点的下一个地址是NULL，所以分开输出
    }
    return 0;
}

A1074

1074 Reversing Linked List (25分)

NTaurus