给定一个常数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是下一结点的地址。
输出格式:
对每个测试用例,顺序输出反转后的链表,其上每个结点占一行,格式与输入相同。
输入样例:
1 2 3 4 5 6 7 |
00100 6 4 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218 |
输出样例:
1 2 3 4 5 6 |
00000 4 33218 33218 3 12309 12309 2 00100 00100 1 99999 99999 5 68237 68237 6 -1 |
题目的Address可以通过字符串或整形变量进行储存。
同时,所给的节点不一定都在链表上,注意这一点即可AC~
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#include<stdio.h> #include<stdlib.h> #include<memory.h> typedef struct { int address; int data; int next; } list; int main() { int n,k,i,j,start,count=1; list *in,*out,temp,*po; scanf("%d%d%d",&start,&n,&k); in=(list *)malloc(n*sizeof(list)); out=(list *)malloc(n*sizeof(list)); po=NULL; for(i=0;i<n;i++) { scanf("%d%d%d",&in[i].address,&in[i].data,&in[i].next); if(start==in[i].address) { memcpy(&out[0],&in[i],sizeof(list)); po=out; } else if(po!=NULL&&po->next==in[i].address) { memcpy(po+1,&in[i],sizeof(list)); count++; po++; } } /* for(i=0;i<n-1;i++) { for(j=0;j<n;j++) { if(out[i].next==in[j].address) { memcpy(&out[i+1],&in[j],sizeof(list)); count++; break; } } }*/ while(po->next!=-1) { for(i=0;i<n;i++) { if(po->next==in[i].address) { memcpy(po+1,&in[i],sizeof(list)); count++; po++; break; } } } if(k>1&&k<=count) { for(i=0;i<count;i+=k) { if(count-i>=k) { for(j=i;j<i+k/2;j++) { memcpy(&temp,&out[j],sizeof(list)); memcpy(&out[j],&out[i+i+k-j-1],sizeof(list)); memcpy(&out[i+i+k-j-1],&temp,sizeof(list)); } } else { break; } } for(i=0;i<count-1;i++) { out[i].next=out[i+1].address; printf("%05d %d %05d\n",out[i].address,out[i].data,out[i].next); } out[i].next=-1; printf("%05d %d %d\n",out[i].address,out[i].data,out[i].next); } else { for(i=0;i<count-1;i++) { printf("%05d %d %05d\n",out[i].address,out[i].data,out[i].next); } printf("%05d %d %d\n",out[i].address,out[i].data,out[i].next); } free(in); free(out); } |
所以说这道题不用写链表也能做出来吗?
你所理解的链表是什么?
链表的实现方式不只有那么一种呀