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.
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤10^5) 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:
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.
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
代码实现 C语言 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 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 #include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct Node *List; struct Node { char Address[6]; int Data; char Next[6]; List link; }; List ReadList() { // 按输入顺序读入，并存为链表 List L, p; int N; L = (List)malloc(sizeof(struct Node)); p = L; scanf("%s %d %d", L->Next, &N, &(L->Data)); for ( int i=0; i<N; i++ ) { List t = (List)malloc(sizeof(struct Node)); scanf("%s %d %s", t->Address, &(t->Data), t->Next); t->link = NULL; p->link = t; p = t; } return L; } List SearchList( List L, char Next[] ) { // 查找结点的下一个节点，用在SortList函数中 List p, t; p = L; // 标记当前操作节点 t = L; // 标记当前操作节点的前一节点，方便找到要找的节点后删除该节点 if ( p->link ) { while ( p->link ) { p = p->link; if ( strcmp(p->Address, Next) == 0 ) { t->link = p->link; // 删除找到的节点，节点数据多时加快以后的查找速度 p->link = NULL; // 初始化返回节点的link指针 break; } t = t->link; } } return p; } List SortList( List L ) { //将输入的节点按Address，Next的顺序排序并返回 List p, tmp, Lout; //p标记返回List，tmp标记查找到的节点，Lout标记返回的List的空间 Lout = (List)malloc(sizeof(struct Node)); Lout->Data = L->Data; // 头结点的Data字段存放反转个数K strcpy(Lout->Next, L->Next); // 初始化返回List的开始节点 p = Lout; // 从原乱序List表中查找节点并拼接到返回Lout中 while ( strcmp(p->Next, "-1") != 0 ) { // Next="-1"为List表最后一个节点的标识 tmp = SearchList( L, p->Next ); // 查找并返回前一个节点所指的下一个节点 if ( tmp ) { // 将返回的节点接到Lout最后 tmp->link = NULL; p->link = tmp; p = tmp; } } return Lout; } List Push( List Stack, List tmp ) { // 堆栈压入方法 List s, p; s = Stack; p = (List)malloc(sizeof(struct Node)); if ( s->link ) { s = s->link; strcpy(p->Address, tmp->Address); p->Data = tmp->Data; strcpy(p->Next, tmp->Next); p->link = s; Stack->link = p; } else { strcpy(p->Address, tmp->Address); p->Data = tmp->Data; strcpy(p->Next, tmp->Next); p->link = NULL; Stack->link = p; } return Stack; } List Pop( List Stack ) { // 堆栈弹出方法 List s; s = Stack; if ( s->link ) { s = s->link; Stack->link = s->link; strcpy(s->Next, "-1"); // pop出来时将List节点的Next值初始化为"-1" s->link = NULL; return s; } else { return NULL; } } List ReverseList( List L ) { // 反转并输出排序好的List List Lout, Stack, p, s, mark, t; // t存放堆栈取出的节点 // 输出链表初始化 Lout = (List)malloc(sizeof(struct Node)); Lout->link = NULL; strcpy(Lout->Next, "-1"); // 初始化一个堆栈用于反向 Stack = (List)malloc(sizeof(struct Node)); Stack->link = NULL; p = L; // 取出原链表节点的标记，用于堆栈push mark = L; // 已处理原链表节点的标记 s = Lout; // 输出链表的标记 if ( p->link ) { int K = L->Data; //需要反向的节点个数 int flag = 0; //已压入堆栈的节点个数 // 从原链表取出节点并压入堆栈，每K个从堆栈取出并插入到输出链表后。 while( p->link ) { p = p->link; if ( flag < K ) { // 压入堆栈 Stack = Push(Stack, p); flag++; // 标记已压入堆栈的节点数 } else { for ( int i=K; i>0; i-- ) { // 达到K个后一次性弹出 t = Pop(Stack); s->link = t; strcpy(s->Next, t->Address); //将前一个节点的Next值标记为下一个节点的Address值 s = t; // 移动插入标记到插入好的节点 mark = mark->link; // 每处理好一个移动一次原链表的标记指针。方便最后不足K个节点的处理 } Stack = Push(Stack, p); // 输出完以后压入本次循环的原链表节点 flag = 1; // 初始化已压入堆栈节点数为1 } } if ( mark->link && flag != K ) { // 剩余的节点不足K个，则按原链表顺序输出 while( mark->link ) { // 处理，直到最后一个节点 mark = mark->link; // 直接取原链表节点操作 s->link = mark; strcpy(s->Next, mark->Address); s = mark; } } else { // 如果最后正好有K个节点压入堆栈，则没有输出，需要将堆栈中的节点全部输出 for ( int i=K; i>0; i-- ) { t = Pop(Stack); s->link = t; strcpy(s->Next, t->Address); s = t; } } } return Lout; } void Print( List L ) { // 打印函数 List p = L; if ( p->link ) { while ( p->link ) { p = p->link; printf("%s %d %s\n", p->Address, p->Data, p->Next); } } } int main() { List L, Lout1, Lout2; L = ReadList(); // 读入节点顺序，保存为链表 Lout1 = SortList( L ); // 按Address、Next顺序排序，并保存为新链表 Lout2 = ReverseList( Lout1 ); // 每K个反向，并保存为新链表 Print(Lout2); // 打印处理好的链表 return 0; }
