02-线性结构1. Reversing Linked List

题目链接： 

答案错误，存一下，留作比较

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

typedef struct node
{
    char Address[6] ;
    int Data ;
    char Next[6] ;
}Node ;

void reverse ( int from , int to , int *arr )
{
    int temp ;
     for ( int i = 0 ; i <= (to - from )/2 ; i++ )
     {
         temp = arr[i+from] ;
         arr[i+from] = arr [to-i] ;
        arr[to-i] = temp ;
     }
}

void Reverse ( int K , int N , int *arr )
{

    for ( int i = 0 ; i < (int)(N/K) ;i++ )
    {
        reverse( i*K , (i+1)*K - 1, arr ) ;
    }
}


int main ( void )
{
    Node *nodeList = NULL ;

    int pList [100001] ,N , K ; // is the length of list , K is the reverse unit
    char first[6] , *next;

    scanf ("%s%d%d" , first , &N , &K ) ;

    memset (pList , 0 , sizeof(pList)) ;

    nodeList = (Node*)malloc (N*sizeof(Node) ) ;

    for ( int i = 0 ; i < N ; i++ )
    {
        scanf ("%s%d%s" , nodeList[i].Address , &nodeList[i].Data ,nodeList[i].Next ) ;

        if ( strcmp(first , nodeList[i].Address) == 0 ) // find first
            pList[0] = i ;
    }

    next = nodeList[ pList[0] ].Next ;
    int counter = 1 ;
    while ( counter != N )
    {
     for ( int j = 0 ; j < N ; j++ )
        {
            if ( strcmp( next , nodeList[j].Address )== 0 )
            {
                pList[counter++] = j ;
                next = nodeList[j].Next ;
            }
        }
    }


    Reverse ( K, N, pList ) ;

    for ( int i = 0 ; i < N ; i++ )
        printf ("%d " , nodeList [pList[i] ].Data ) ;

     for ( int i = 0 ; i < N-1 ; i++ )
     {
        strcpy(    nodeList[pList[i]].Next ,nodeList[pList[i+1]].Address) ;
     }

     for ( int i = 0 ; i < N ; i++ )
    {
     printf ("%s %d %s" , nodeList[pList[i]].Address , nodeList[pList[i]].Data , nodeList[pList[i] ].Next) ;

         if ( i != N -1 )
           printf ("\n") ;
        }

    return 0 ;
}

---

第二次提交代码： 一个测试点没有过， 运行超时，我觉得应该是翻转数组的方法不妥当。

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

typedef struct node
{
    char Address[6] ;
    int Data ;
    char Next[6] ;
}Node ;

void reverse ( int from , int to , int *arr )
{
    int temp ;
     for ( int i = 0 ; i <= (to - from )/2 ; i++ )
     {
         temp = arr[i+from] ;
         arr[i+from] = arr [to-i] ;
        arr[to-i] = temp ;
     }
}

void Reverse ( int K , int N , int *arr )
{
       if ( K == 0 || K == 1 )
     return ;

    for ( int i = 0 ; i < (int)(N/K) ;i++ )
    {
        reverse( i*K , (i+1)*K - 1, arr ) ;
    }
}


int main ( void )
{
    Node *nodeList = NULL ;

    int pList [100001] ,N , K ; // is the length of list , K is the reverse unit
    char first[6] , *next;

    scanf ("%s%d%d" , first , &N , &K ) ;

    memset (pList , 0 , sizeof(pList)) ;

    nodeList = (Node*)malloc (N*sizeof(Node) ) ;

    for ( int i = 0 ; i < N ; i++ )
    {
        scanf ("%s%d%s" , nodeList[i].Address , &nodeList[i].Data ,nodeList[i].Next ) ;

        if ( strcmp(first , nodeList[i].Address) == 0 ) // find first
            pList[0] = i ;
    }

    next = nodeList[ pList[0] ].Next ;
    int counter = 1 ;
    while ( counter != N )
    {
     for ( int j = 0 ; j < N ; j++ )
        {
            if ( strcmp( next , nodeList[j].Address )== 0 )
            {
                pList[counter++] = j ;
                next = nodeList[j].Next ;
            }
        }
    }


    Reverse ( K, N, pList ) ;



     for ( int i = 0 ; i < N-1 ; i++ )
    {
     printf ("%s %d %s\n" , nodeList[pList[i]].Address , nodeList[pList[i]].Data , nodeList[pList[i+1] ].Address) ;
        }
      printf ("%s %d -1" , nodeList[pList[N-1]].Address , nodeList[pList[N-1]].Data ) ;

    return 0 ;
}