3-5 单链表分段逆转 (20分)

3-5 单链表分段逆转 (20分)

给定一个带头结点的单链表和一个整数K，要求你将链表中的每K个结点做一次逆转。例如给定单链表 1→2→3→4→5→6 和 K=3，你需要将链表改造成 3→2→1→6→5→4；如果 K=4，则应该得到 4→3→2→1→5→6。

函数接口定义：

void K_Reverse( List L, int K );

其中List结构定义如下：

typedef struct Node *PtrToNode; struct Node { ElementType Data; /* 存储结点数据 */ PtrToNode Next; /* 指向下一个结点的指针 */ }; typedef PtrToNode List; /* 定义单链表类型 */

L是给定的带头结点的单链表，K是每段的长度。函数K_Reverse应将L中的结点按要求分段逆转。

裁判测试程序样例：

#include <stdio.h> #include <stdlib.h> typedef int ElementType; typedef struct Node *PtrToNode; struct Node { ElementType Data; /* 存储结点数据 */ PtrToNode Next; /* 指向下一个结点的指针 */ }; typedef PtrToNode List; /* 定义单链表类型 */ List ReadInput(); /* 裁判实现，细节不表 */ void PrintList( List L ); /* 裁判实现，细节不表 */ void K_Reverse( List L, int K ); int main() { List L; int K; L = ReadInput(); scanf("%d", &K); K_Reverse( L, K ); PrintList( L ); return 0; } /* 你的代码将被嵌在这里 */

输入样例：

6 1 2 3 4 5 6 4

输出样例：

4 3 2 1 5 6

AC代码：

我的想法：

今天在实验室写了好久呢，刚开始的时候错了好多次，后来发现最后的转置没有做好，改了一下久成功啊。 最后在吐槽一下我自己：每次这种转置你都用一个数组存储所有的元素，然后按照要求什么的倒叙赋值，效率太低，但是我这思想素质，也只能想到这种方法，以后要改进啊！！！

void K_Reverse( List L, int K ) { int i,j,x,s; List p=L->Next; List t=p; for(i=0; t!=NULL; i++) { //用i记录整个链表的长度 t=t->Next; } if(K<=1||K>i) return ; x=i/K; int A[x]; while(x--) { i=K; j=0; t=p; while(i--) { A[j++]=p->Data; p=p->Next; } while(j--) {//是刚开始的时候这里写错了，应该反向赋值 t->Data=A[j]; t=t->Next; } } }