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

链表题真恶心，不会做。。。指针指来指去，走个神就更啥都不会了。。

void K_Reverse( List L, int K ){ if(!L||K<=1) return; int len = 0; List ptr = L->Next; while(ptr){ len++; ptr = ptr->Next; } List p = L,q,r,tmp;//p保存上一个，q指示当前，r指向下一个 for(int i = 0;i<len/K;i++){//分段逆转次数 q = p->Next; r = q->Next; ptr = q; //逆转 ，注意在进入第一层for循环之后，已经对指针进行了定位，所以逆转时循环k-1次即可 for(int j = 1;j<K;j++){ tmp = r->Next; r->Next = q; q = r; r = tmp; } p->Next = q; ptr->Next = r; p = ptr; } }