给定一个带头结点的单链表和一个整数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 );
裁判测试程序样例:
#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; } /* 你的代码将被嵌在这里 */
L
是给定的带头结点的单链表,K
是每段的长度。函数K_Reverse
应将L中的结点按要求分段逆转。
输入样例:
6 1 2 3 4 5 6 4
输出样例:
4 3 2 1 5 6
解题代码:
void K_Reverse( List L, int K ) { List p=L,q=L->Next,oldh,newh,temp,t; int count=0,j; while(q) { count++; q=q->Next; } if(count==0||K<=1||K>count) return; for(int i=0;i<count/K;i++) { j=1; newh=p->Next; oldh=newh->Next; t=newh; while(j!=K) { temp=oldh->Next; oldh->Next=newh; newh=oldh; oldh=temp; j++; } p->Next=newh; t->Next=oldh; p=t; } }