给定一个带头结点的单链表和一个整数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 )
{
    List p,t,tail,new,old,tmp;
    p=L->Next;
    int cnt1=0,cnt2,cnt3;
    while(p)  //遍历链表有几个数
    {
        cnt1++;
        p=p->Next;
    }
    cnt2=cnt1/K; //逆转几次
    if(K==1||cnt2==0)//如果K=1或者K超过表长，不反转
    {
        return;
    }
    else //否则链表至少含有2个数且K不超表长
    {
        new=L->Next;
        old=new->Next;
        tail=L;
        while(cnt2>0)//循环处理每一段的逆转
        {
            cnt3=1;
            t=new;  //t为临时变量，保留每段开始结点的位置
            while(cnt3<K) //K个结点进行逆转
            {
                tmp=old->Next;
                old->Next=new;
                new=old;
                old=tmp;
                cnt3++;
            }
            t->Next=old; //将这一段的尾结点指针指向下一段的开始结点
            tail->Next=new; //将上一段的尾结点指针指向这一段的开始结点
            tail=t; //更新每一段逆转结束后尾结点的位置
            cnt2--;
            if(old==NULL) //如果链表后面没有数，直接跳出循环
            {
                break;
            }
            else //否则更新new，old位置，开始下一段的逆转
            {
                new=old;
                old=old->Next;
            }
        }
    }
}

另外两个函数参考代码：

List ReadInput()
{
    List head,tail,p;
    head=(List)malloc(sizeof(struct Node));
    head->Next=NULL;
    tail=head;
    int i,n;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        p=(List)malloc(sizeof(struct Node));
        scanf("%d",&p->Data);
        p->Next=NULL;
        tail->Next=p;
        tail=p;
    }
    return head;
}

void PrintList( List L )
{
    List p;
    p=L->Next;
    while(p)
    {
        printf("%d ",p->Data);
        p=p->Next;
    }
}

思路：

• 从某个头结点开始，将随后的K个结点进行逆转，视频中姥姥给出了详细的讲解；
• 逆转一段子链表的头尾指针，这里可以参考代码及注释，建议画出图来，便于理解。

注意： 当尾部结点不到K个结点时，不进行逆转。所以在执行逆转之前，先判断链表中有几个结点，需要几次的逆转。