1025 反转链表 (25 分) c语言实现+测试点

1025 反转链表 (25 分) c语言实现+测试点

题目

1025 反转链表 (25 分)

给定一个常数 K 以及一个单链表 L，请编写程序将 L 中每 K 个结点反转。例如：给定 L 为 1→2→3→4→5→6，K 为 3，则输出应该为 3→2→1→6→5→4；如果 K 为 4，则输出应该为 4→3→2→1→5→6，即最后不到 K 个元素不反转。

输入格式：

每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤105)、以及正整数 K (≤N)，即要求反转的子链结点的个数。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。

接下来有 N 行，每行格式为：

 Address Data Next

其中 Address 是结点地址，Data 是该结点保存的整数数据，Next 是下一结点的地址。 

输出格式：

对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。

输入样例：

00100 6 4

00000 4 99999

00100 1 12309

68237 6 -1

33218 3 00000

99999 5 68237

12309 2 33218

输出样例： 

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

   

    博主个人思路并没有采用结构体中放结构体地址的做法，而是用另一种方法记录了链表中数据的位置，其实跟直接放地址差不多，都起到了链表的作用，细节写在注释里，关于特定的测试点写在文章最后，欢迎批评。

#include
typedef struct shuju
    {int address;     
     int data;        
     int next;        
     int before;      
    }stu;
int main(){
    stu a[100001];      
    stu *b[100001];    
    int add,ad,n,k,i,data,next,l;
    scanf("%d %d %d",&add,&n,&k);    
    for(i=0;il)       
                    {if(i!=l)    
                        printf("%05d %d %05dn",b[i-x]->address,b[i-x]->data,b[i]->next);
                     else
                         printf("%05d %d %dn",b[i-x]->address,b[i-x]->data,b[i]->next);
                    }
                 else
                    {printf("%05d %d %05dn",b[i-x]->address,b[i-x]->data,b[i-1+k]->next);
                    }
                }
             else
                printf("%05d %d %05dn",b[i-x]->address,b[i-x]->data,b[i-x]->before);
            }
        }
        i=i-k+1;
    for(;i<=l;i++)     
        if(b[i]->next==-1)
            printf("%05d %d %dn",b[i]->address,b[i]->data,b[i]->next);
        else
            printf("%05d %d %05dn",b[i]->address,b[i]->data,b[i]->next);
    return 0;
}

 测试点分析

    测试点0是总长度不到2*K的常规项，此项错误说明程序反转存在问题。

    测试点1 2 3 4要注意最后输出的-1，且不要重复输出，似乎使长度为K的整数倍的测试例。

    测试点5是一个比较大的测试例（可以看下面图片的测试结果，运行内存和时间相对都比较大），这个如果超时说明代码不够简洁，过于复杂。

    测试点6的关键在于不要把节点总个数当作从起始节点开始的长度，即起始节点不一定是表头。

注意点 

1.题目要求每K个反转，并不是前四个反转。

2.最后若不足K个，不反转。

3.注意最后一项的输出，-1不要输出成-10001

4.不要把节点总个数当作从起始节点开始的长度，起始节点不一定是表头。

 改了几次勉强过了，测试点6审题问题着实费了不少时间。

 但这个时候有小伙伴就要说了，你这也没真的反转啊，只是这么输出了而已。但其实只要在每一个printf的地方用另一个结构体组储存就可以，然后最后一起输出也是一样的，因为是做pat，只要求最后的输出，所以干脆偷懒啦。