首页 > 代码库 > [PAT] 02-线性结构2 Reversing Linked List(单向链表的逆转) - C语言实现
[PAT] 02-线性结构2 Reversing Linked List(单向链表的逆转) - C语言实现
今天突然想起自己的cnblog有差不多一年没更了??放一道很久前做的也写好了很久但是一直忘记发布的题.如果有不同的算法欢迎分享~
[PAT]02-线性结构2 Reversing Linked List (25分)
Given a constant KK and a singly linked list LL, you are supposed to reverse the links of every KK elements on LL. For example, given LL being 1→2→3→4→5→6, if K = 3K=3, then you must output 3→2→1→6→5→4; if K = 4K=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 NN (\le 10^5≤10?5??) which is the total number of nodes, and a positive KK (\le N≤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 NN lines follow, each describes a node in the format:
Address Data Nextwhere
Addressis the position of the node,Datais an integer, andNextis 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:
00100 6 400000 4 9999900100 1 1230968237 6 -133218 3 0000099999 5 6823712309 2 33218Sample Output:
00000 4 3321833218 3 1230912309 2 0010000100 1 9999999999 5 6823768237 6 -1
1 #include <stdio.h> 2 #include <malloc.h> 3 4 typedef struct _node 5 { 6 int data; 7 int address; 8 int back; 9 int next; 10 // int flag; 11 } NODE; 12 NODE* List[100001]={0}; 13 int main(void) 14 { 15 int FirstAddr,TotalNode,NumberToReverse,i; 16 int AddrTemp,DataTemp,NextAddrTemp; 17 int Loop,Mod; 18 int count=0; 19 int Boundary; 20 NODE* LinkFix=NULL; 21 NODE* EachNode=NULL; 22 scanf("%d %d %d",&FirstAddr,&TotalNode,&NumberToReverse); 23 24 int* AddrInOrder=(int *)calloc(TotalNode+1,sizeof(int)); 25 int* LinkReverse=(int *)calloc(TotalNode+1,sizeof(int)); 26 for (i=0; i<TotalNode; i++) 27 { 28 scanf("%d %d %d",&AddrTemp,&DataTemp,&NextAddrTemp); 29 EachNode=(NODE*)calloc(1,sizeof(NODE)); 30 *(List+AddrTemp) = EachNode; 31 EachNode -> address = AddrTemp; 32 EachNode -> data =http://www.mamicode.com/ DataTemp; 33 EachNode -> next = NextAddrTemp; 34 } 35 36 i=0; 37 LinkFix = *(List+FirstAddr); 38 while (1) 39 { 40 *(AddrInOrder+i) = LinkFix -> address; 41 if (LinkFix -> next == -1) break; 42 // (*(List+(LinkFix->next)))->back = LinkFix -> address; 43 LinkFix = *(List+(LinkFix -> next)); 44 i++; 45 } 46 TotalNode=i+1; 47 // printf("\n"); 48 // for (i=0; i<TotalNode; i++) printf("%05d\n",*(AddrInOrder+i)); 49 Mod = TotalNode % NumberToReverse; 50 // Multily = TotalNode / NumberToReverse; 51 Loop=NumberToReverse; 52 if (NumberToReverse != 1) 53 { 54 for (i=0;i<=TotalNode-Mod-1;) 55 { 56 if ( count == Loop ) 57 { 58 count=0; 59 i=Loop+i; 60 } 61 if (i >= TotalNode-Mod-1) break; 62 *(LinkReverse+i+count) = *(AddrInOrder+i+(Loop-count-1)); 63 count++; 64 } 65 Boundary=i; 66 } 67 else for (i=0;i<=TotalNode-1;i++) *(LinkReverse+i) = *(AddrInOrder+i); 68 69 70 71 if (Mod) 72 for (i=Boundary; i<TotalNode; i++) 73 { 74 *(LinkReverse+i)=*(AddrInOrder+i); 75 if ( i == TotalNode-1 ) (*(List+*(LinkReverse+i)))->next = -1; 76 77 } 78 79 else 80 { 81 // for (i= TotalNode/2 -1 ; i<TotalNode; i++) 82 if (TotalNode == 1) ; 83 else 84 { 85 (*(List+*(LinkReverse+TotalNode-Loop)))->next = (*(List+*(LinkReverse+TotalNode-Loop+1)))->address; 86 (*(List+*(LinkReverse+TotalNode-1)))->next = -1; 87 (*(List+*(LinkReverse)))->next = (*(List+*(LinkReverse+1)))->address; 88 } 89 } 90 91 // printf("\n"); 92 // for (k=0; k<TotalNode; k++) printf("%05d\n",*(LinkReverse+k)); 93 94 if (TotalNode>1) 95 for (i=0; i<TotalNode; i++) 96 { 97 if ((*(List+*(LinkReverse+i)))->next == -1) 98 { 99 printf("%.5d %d -1\n",*(LinkReverse+i),(*(List+*(LinkReverse+i)))->data);100 }101 else 102 {103 printf("%.5d %d %.5d\n",*(LinkReverse+i),(*(List+*(LinkReverse+i)))->data,(*(List+*(LinkReverse+i+1)))->address);104 }105 106 }107 else printf("%.5d %d -1\n",*(LinkReverse),(*(List+*(LinkReverse)))->data);108 109 110 // free(AddrInOrder);111 // free(LinkReverse);112 return 0; 113 114 }
提交结果:
测试点6空间消耗很大.以后有时间再优化吧~(立了一个大flag)
[PAT] 02-线性结构2 Reversing Linked List(单向链表的逆转) - C语言实现