给定一个常数 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 (≤10?5??)、以及正整数 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<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{int adde; //地址int data; //结点数据int next; //下一个结点地址
};int first,n,k; //首结点地址，结点数，k个结点反转
struct node link[100007];
struct node link1[100007];
struct node link2[100007];
int main()
{scanf("%d%d%d",&first,&n,&k); for(int i=0;i<n;i++){scanf("%d%d%d",&link[i].adde,&link[i].data,&link[i].next); }int count=0;//统计有效的结点数 while(first!=-1) //先按照地址的顺序将结点连接起来 {for(int j=0;j<n;j++){if(link[j].adde==first){link1[count]=link[j];first=link1[count].next;count++;}} } int c=count/k; //一共反转的次数 int ind=0;for(int i=0;i<c;i++){for(int j=(i+1)*k-1;j>=i*k;j--){link2[ind]=link1[j];ind++;}} for(int i=ind;i<count;i++) //剩下的没反转的结点link2[i]=link1[i];for(int i=0;i<count-1;i++) //改变反转之后每个结点的下一个结点的地址{link2[i].next=link2[i+1].adde;}link2[count-1].next=-1; //最后的结点的next为-1for(int i=0;i<count-1;i++){printf("%05d %d %05d\n",link2[i].adde,link2[i].data,link2[i].next);}printf("%05d %d %d\n",link2[count-1].adde,link2[count-1].data,link2[count-1].next);return 0;
}
代码二：（使用现成的反转函数reverse）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{int adde; //地址int data; //结点数据int next; //下一个结点地址
};int first,n,k; //首结点地址，结点数，k个结点反转
struct node link[100007];
struct node link1[100007];
struct node link2[100007];
int main()
{scanf("%d%d%d",&first,&n,&k); for(int i=0;i<n;i++){scanf("%d%d%d",&link[i].adde,&link[i].data,&link[i].next); }int count=0;//统计有效的结点数 while(first!=-1) //先按照地址的顺序将结点连接起来 {for(int j=0;j<n;j++){if(link[j].adde==first){link1[count]=link[j];first=link1[count].next;count++;}} } for(int i=0;i<(count-count%k);i+=k){ //反转reverse(link1+ i, link1 + i + k);} for(int i=0;i<count-1;i++){link1[i].next=link1[i+1].adde; //改变反转之后的结点的next的地址}link1[count-1].next=-1; for(int i=0;i<count-1;i++){printf("%05d %d %05d\n",link1[i].adde,link1[i].data,link1[i].next);}printf("%05d %d %d\n",link1[count-1].adde,link1[count-1].data,link1[count-1].next);return 0;
}
代码三：（数组下标为结点地址+反转函数reverse）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{int data;int next;
};
struct node list[100007];
int list1[100007];
int main()
{int first,k,n;int tem;scanf("%d%d%d",&first,&n,&k);for(int i=0;i<n;i++){scanf("%d",&tem);scanf("%d%d",&list[tem].data,&list[tem].next);}int count=0;while(first!=-1) //将结点的地址按顺序连接 {list1[count++]=first;first=list[first].next;}for(int i=0;i<(count-count%k);i+=k) //反转 {reverse(list1+i,list1+i+k);} for(int i=0;i<count-1;i++){printf("%05d %d %05d\n",list1[i],list[list1[i]].data,list1[i+1]);} printf("%05d %d -1\n",list1[count-1],list[list1[count-1]].data);return 0;
}