02-线性结构3 Reversing Linked List

02-线性结构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 Lbeing 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

Code:

#include <stdio.h>

#define MAX 100000

typedef struct{

    int data;

    int next;

}Node;

//计算在数组中的元素个数

int CountNum(Node *list,int plist);

//反转元素

int Reverse(Node *list,int num,int plist,int k);

//打印元素

void Print(Node *list,int plist);

int main(){

    Node list[MAX];

    int plist,n,k;

    scanf("%d%d%d",&plist,&n,&k);

    int addr,data,next;

    while(n>0){

        scanf("%d%d%d",&addr,&data,&next);

        list[addr].data=data;

        list[addr].next=next;

        n--;

    }

    int num=CountNum(list,plist);

    int newplist=Reverse(list,num,plist,k);

    Print(list,newplist);

    return 0;

}

int Reverse(Node *list,int num,int plist,int k){

    int preNode,curNode,nextNode;

    preNode=-1;

    curNode=plist;

    nextNode=list[curNode].next;

    int head=-1,lasthead;

    for (int i=0;i<num/k;i++){

        lasthead=head;

        head=curNode;

        for(int j=0;j<k;j++){

            list[curNode].next=preNode;

            preNode=curNode;

            curNode=nextNode;

            nextNode=list[curNode].next;

        }

        if (i==0) plist=preNode;

        else list[lasthead].next=preNode;

    }

    list[head].next = curNode; //不用逆转的剩余部分加上

    return plist;

}

int CountNum(Node *list,int plist){

    int c=1;

    while((plist=list[plist].next)!=-1) c++;

    return c;

}

void Print(Node *list,int plist){

    while((list[plist].next)!=-1){

        printf("%05d %d %d\n",plist,list[plist].data,list[plist].next);

        plist = list[plist].next;

    }

    printf("%05d %d %d\n",plist,list[plist].data,list[plist].next);

}