02-线性结构3 Reversing Linked List

Given a constant and a singly linked list , you are supposed to reverse the links of every elements on . For example, given L being 1→2→3→4→5→6, if =3, then you must output 3→2→1→6→5→4; if =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 which is the total number of nodes, and a positive 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

My Code

#include<stdio.h>
int main()
{
    int address,faddress,data,next,n,k,i,j,count,sum=0;
    scanf("%d %d %d",&faddress,&n,&k);
    int link[n][3];
    for(i=0; i<n; i++){  //读取数据 
        scanf("%d %d %d",&address,&data,&next);
        link[i][0] = address;
        link[i][1] = data;
        link[i][2] = next;
    }
    int tmpad,tmpda,tmpne,ne=faddress;
    for(i=0; i<n; i++){  //让数据在数组中按照顺序存放 
        for(j=i; j<n; j++){
            if(link[j][0] == ne){
                count = j;
                break;
            }
        }
        ne = link[count][2];sum = sum + 1;  //sum是为了去除多余的，并不在链表里面的结点 
        tmpad = link[i][0];tmpda = link[i][1];tmpne = link[i][2];
        link[i][0] = link[count][0];link[i][1] = link[count][1];link[i][2] = link[count][2];
        link[count][0] = tmpad;link[count][1] = tmpda;link[count][2] = tmpne;
        if(ne==-1) break;
    }
    int newlink[sum][3];
    for(i=sum; i>=1; i--){  //按照要求逆序存放，此时只对链表中的结点进行操作 
        if(i%k==0){
            for(j=1; j<k; j++){
                newlink[(i/k-1)*k+j-1][0] = link[i-j][0];
                newlink[(i/k-1)*k+j-1][1] = link[i-j][1];
                newlink[(i/k-1)*k+j-1][2] = link[i-j-1][0];
            }
            newlink[(i/k-1)*k+k-1][0] = link[i-k][0];
            newlink[(i/k-1)*k+k-1][1] = link[i-k][1];
            if(i==sum) newlink[(i/k-1)*k+k-1][2] = -1;
            else newlink[(i/k-1)*k+k-1][2] = newlink[i][0];
        }
        if(i%k!=0 && i==sum){
            for(j=1;j<=i%k;j++){
                newlink[i-j][0] = link[i-j][0];
                newlink[i-j][1] = link[i-j][1];
                if(j==1) newlink[i-j][2] = -1;
                else newlink[i-j][2] = link[i-j][2];
            }
        }
    }
    for(i=0;i<sum-1;i++) printf("%05d %d %05d\n",newlink[i][0],newlink[i][1],newlink[i][2]);
    printf("%05d %d -1\n",newlink[sum-1][0],newlink[sum-1][1]);
    return 0;
} 

outcome

thoughts

这个题目实际上并不是特别难，我是独立完成整个题目的，但是值得注意的是需要注意很多细节，不然很多测试点都无法通过，并且要注意算法的时间与空间复杂度，由于的最大值可以取到,如果算法太过于暴力肯定是不行的，实际上我的这个算法就稍微有一点暴力了，只要去掉其中一句关键用于减少时间复杂度的语句就会不通过时间测试。