Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K = 3, then you must output 3→2→1→6→5→4; if K = 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 N (<= 105) which is the total number of nodes, and a positive K (<=N) 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:
|
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 |
Sample Output:
|
1 2 3 4 5 6 |
00000 4 33218 33218 3 12309 12309 2 00100 00100 1 99999 99999 5 68237 68237 6 -1 |
PAT-Basic-1025. 反转链表的英文版。
代码如下：
|
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); } |