题目
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<stdio.h>
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;i<n;i++) /*记录数据*/{scanf("%d %d %d",&ad,&data,&next);a[ad].address=ad;a[ad].data=data;a[ad].next=next;a[next].before=ad;}for(i=1;1;i++){b[i]=&a[add];l=i; /*l用来记录从起始节点到链表最后的长度*/add=a[add].next;if(add==-1) /*测试点六的决定位置*/break;}for(i=k;i<=l;i=i+k){for(int x=0;x<k;x++){if(x==k-1) /*每K个的最后一个，转换后的该位置的下一个并不是转换前该位置的前一个，似乎有点绕...*/{if(i+k>l) /*考虑此后不足k个不反转的情况*/{if(i!=l) /*这里没有if判定会导致测试点1 2 3 4错误，-1输出会有问题*/printf("%05d %d %05d\n",b[i-x]->address,b[i-x]->data,b[i]->next);elseprintf("%05d %d %d\n",b[i-x]->address,b[i-x]->data,b[i]->next);}else{printf("%05d %d %05d\n",b[i-x]->address,b[i-x]->data,b[i-1+k]->next);}}elseprintf("%05d %d %05d\n",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 %d\n",b[i]->address,b[i]->data,b[i]->next);elseprintf("%05d %d %05d\n",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，只要求最后的输出，所以干脆偷懒啦。