基礎實驗3-2.2 單連結清單分段逆轉 (25分)

給定一個帶頭結點的單連結清單和一個整數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                



//最好手動模拟2個逆轉，每個逆轉k個元素，一切就會明白了      

void K_Reverse( List L, int K )//前k個結點前插，後面若還有的話就連上去
{
    int cnt;
    int len = 0;
    List p=L, r, s, t ,q = p->Next,tmp; 
    while(q)//q指向首結點
    {
        q = q->Next;
        len++;
    }
    
    if(!len || K>len||K<=1)//len=0根本不需要逆轉
        return;
    
    for(int i=0;i<len/K;i++)
    {
        cnt=1;
        r= p->Next;//r是已經逆轉的首節點
        s =r->Next;//s是未逆轉連結清單的首結點
        t = r;//t指向每一輪逆轉的第一個結點，逆轉後就變成了最後一個結點
        
        while(cnt!=K)
        {
            tmp = s->Next;
            s->Next = r;
            r =s;
            s =tmp;
            cnt++;
        }//跳出while()說明一輪逆轉結束
        
        p ->Next = r;//p->next指向新的頭節點
        t ->Next =s;//逆轉後的k個結點的尾結點指向下一個逆轉的k個節點尾節點
        p = t;//p指向k個結點的尾結點
    }
    
    
}