leecode-C语言实现-25. K 个一组翻转链表

一、题目

二、解题思路

例如：
链表为：1 -> 2 -> 3 -> 4 -> 5。
步长为：3

（0）定义变量

TmpPoint：来记录当前的链表位置。
PreviousPoint：来记录上一个数组索引位为0的链表地址。
NextPoint：记录当前数组索引位为2的元素链接的下一个链表地址。
TmpArray：初始化一个长度为3的数组，里面存储链表中元素的指针。

（1）循环第一次

TmpPoint：&1
PreviousPoint：NULL
NextPoint：NULL
TmpArray：{&1，null，null}

（2）循环第二次

TmpPoint：&2
PreviousPoint：NULL
NextPoint：NULL
TmpArray：{&1，&2，null}

（3）循环第三次

TmpPoint：&3
PreviousPoint：NULL
NextPoint：&4
TmpArray：{&1，&2，&3}

将数组倒序遍历链接一遍，链表变为：3 -> 2 -> 1 -> 4 -> 5。

（4）循环第四次

TmpPoint：&4
PreviousPoint：&1
NextPoint：&4
TmpArray：{&4，null，null}

（5）循环第五次

TmpPoint：&5
PreviousPoint：&1
NextPoint：&4
TmpArray：{&4，&5，null}

由于元素已经全部遍历完，TmpPoint取下一个地址时取到NULL，退出循环，就得到最终结果啦。

三、VS2017-测试代码

#include 
#include 

#define STEP 2

struct ListNode 
{
    int val;
    struct ListNode *next;
};

typedef struct ListNode LN;

void SwapPoint(LN** TmpArray, LN* PreviousPoint, LN* NextPoint, int step);
struct ListNode* reverseKGroup(struct ListNode* head, int k);
LN* CreateList(int* TestArray, int TestArraySize);
void PrintList(LN* head);
void PrintArray(LN** TmpArray, int TmpArraySize);

int main()
{
    int TestArray[] = { 1,2,3,4,5 };
    int TestArraySize = sizeof(TestArray) / sizeof(int);
    LN* TestList = CreateList(TestArray, TestArraySize);
    PrintList(TestList);
    LN* ResList = reverseKGroup(TestList, STEP);
    PrintList(ResList);
}



struct ListNode* reverseKGroup(struct ListNode* head, int k) 
{
    if (head == NULL)
    {
        return NULL;
    }
    else if (k == 1)
    {
        return head;
    }
    LN** TmpArray = (LN**)malloc(sizeof(LN*) * k);
    LN* HeadPoint = NULL;
    LN* PreviousPoint = NULL;
    LN* NextPoint = NULL;
    LN* TmpPoint = head;
    int i = 0;
    int cnt = 0;

    do
    {
        TmpArray[i] = TmpPoint;
        TmpPoint = TmpPoint->next;
        printf("cnt : %d, i : %dn", cnt, i);
        PrintArray(TmpArray, i+1);
        
        if (cnt == k - 1)
        {
            printf("Head:n");
            HeadPoint = TmpArray[i];
            NextPoint = TmpArray[i]->next;
            PrintArray(TmpArray, k);
            SwapPoint(TmpArray, PreviousPoint,NextPoint, k);
            PreviousPoint = TmpArray[0];
            PrintList(HeadPoint);
            i = -1;
        }
        else if ( (i + 1) % k == 0)
        {
            printf("Continue:n");
            NextPoint = TmpArray[i]->next;
            PrintArray(TmpArray, k);
            SwapPoint(TmpArray, PreviousPoint, NextPoint, k);
            PreviousPoint = TmpArray[0];
            PrintList(HeadPoint);
            i = -1;
        }
        i++;
        cnt++;
    } while (TmpPoint != NULL);
    
    free(TmpArray);
    return HeadPoint;
}

void SwapPoint(LN** TmpArray, LN* PreviousPoint,LN* NextPoint, int step)
{
    int i;
    if (PreviousPoint != NULL)
    {
        PreviousPoint->next = TmpArray[step - 1];
    }
    
    for ( i = step - 1; i >= 1; i--)
    {
        TmpArray[i]->next = TmpArray[i-1];
    }
    TmpArray[i]->next = NextPoint;
}


LN* CreateList(int* TestArray, int TestArraySize)
{
    int i;

    LN* head = (LN*)malloc(sizeof(LN));
    LN* p = (LN*)malloc(sizeof(LN));

    head->val = TestArray[0];
    head->next = NULL;
    p = head;

    for ( i = 1; i < TestArraySize; i++)
    {
        LN* q = (LN*)malloc(sizeof(LN));
        q->val = TestArray[i];
        q->next = NULL;
        p->next = q;
        p = q;
        //free(q);
    }
    //free(p);
    return head;
}

void PrintList(LN* head)
{
    printf("####################################n");
    LN* p = (LN*)malloc(sizeof(LN));
    p = head;
    while (p != NULL)
    {
        printf("CurrentPoint : %p, val : %d, next : %pn",p,p->val,p->next);
        p = p->next;
    }
    free(p);
    printf("####################################n");
}

void PrintArray(LN** TmpArray,int TmpArraySize)
{
    printf("####################################n");
    int i;
    for ( i = 0; i < TmpArraySize; i++)
    {
        printf("i : %d, val : %d, next : %pn",i, TmpArray[i]->val, TmpArray[i]->next);
    }
    printf("####################################n");
}

四、VS2017-测试结果

链表为：1 -> 2 -> 3 -> 4 -> 5。
步长为：2

最终结果为：
链表为：2 -> 1 -> 4 -> 3 -> 5。

C:Usersczg>C:Usersczgsourcereposx64DebugC_TEST.exe
####################################
CurrentPoint : 0000022CCA186790, val : 1, next : 0000022CCA190E00
CurrentPoint : 0000022CCA190E00, val : 2, next : 0000022CCA190E50
CurrentPoint : 0000022CCA190E50, val : 3, next : 0000022CCA190C70
CurrentPoint : 0000022CCA190C70, val : 4, next : 0000022CCA190D60
CurrentPoint : 0000022CCA190D60, val : 5, next : 0000000000000000
####################################
cnt : 0, i : 0
####################################
i : 0, val : 1, next : 0000022CCA190E00
####################################
cnt : 1, i : 1
####################################
i : 0, val : 1, next : 0000022CCA190E00
i : 1, val : 2, next : 0000022CCA190E50
####################################
Head:
####################################
i : 0, val : 1, next : 0000022CCA190E00
i : 1, val : 2, next : 0000022CCA190E50
####################################
####################################
CurrentPoint : 0000022CCA190E00, val : 2, next : 0000022CCA186790
CurrentPoint : 0000022CCA186790, val : 1, next : 0000022CCA190E50
CurrentPoint : 0000022CCA190E50, val : 3, next : 0000022CCA190C70
CurrentPoint : 0000022CCA190C70, val : 4, next : 0000022CCA190D60
CurrentPoint : 0000022CCA190D60, val : 5, next : 0000000000000000
####################################
cnt : 2, i : 0
####################################
i : 0, val : 3, next : 0000022CCA190C70
####################################
cnt : 3, i : 1
####################################
i : 0, val : 3, next : 0000022CCA190C70
i : 1, val : 4, next : 0000022CCA190D60
####################################
Continue:
####################################
i : 0, val : 3, next : 0000022CCA190C70
i : 1, val : 4, next : 0000022CCA190D60
####################################
####################################
CurrentPoint : 0000022CCA190E00, val : 2, next : 0000022CCA186790
CurrentPoint : 0000022CCA186790, val : 1, next : 0000022CCA190C70
CurrentPoint : 0000022CCA190C70, val : 4, next : 0000022CCA190E50
CurrentPoint : 0000022CCA190E50, val : 3, next : 0000022CCA190D60
CurrentPoint : 0000022CCA190D60, val : 5, next : 0000000000000000
####################################
cnt : 4, i : 0
####################################
i : 0, val : 5, next : 0000000000000000
####################################
####################################
CurrentPoint : 0000022CCA190E00, val : 2, next : 0000022CCA186790
CurrentPoint : 0000022CCA186790, val : 1, next : 0000022CCA190C70
CurrentPoint : 0000022CCA190C70, val : 4, next : 0000022CCA190E50
CurrentPoint : 0000022CCA190E50, val : 3, next : 0000022CCA190D60
CurrentPoint : 0000022CCA190D60, val : 5, next : 0000000000000000
####################################

五、leecode提交代码

typedef struct ListNode LN;

void SwapPoint(LN** TmpArray, LN* PreviousPoint, LN* NextPoint, int step);

struct ListNode* reverseKGroup(struct ListNode* head, int k) 
{
    if (head == NULL)
    {
        return NULL;
    }
    else if (k == 1)
    {
        return head;
    }
    LN** TmpArray = (LN**)malloc(sizeof(LN*) * k);
    LN* HeadPoint = NULL;
    LN* PreviousPoint = NULL;
    LN* NextPoint = NULL;
    LN* TmpPoint = head;
    int i = 0;
    int cnt = 0;

    do
    {
        TmpArray[i] = TmpPoint;
        TmpPoint = TmpPoint->next;
        // printf("cnt : %d, i : %dn", cnt, i);
        // PrintArray(TmpArray, i+1);
        
        if (cnt == k - 1)
        {
            // printf("Head:n");
            HeadPoint = TmpArray[i];
            NextPoint = TmpArray[i]->next;
            // PrintArray(TmpArray, k);
            SwapPoint(TmpArray, PreviousPoint,NextPoint, k);
            PreviousPoint = TmpArray[0];
            // PrintList(HeadPoint);
            i = -1;
        }
        else if ( (i + 1) % k == 0)
        {
            // printf("Continue:n");
            NextPoint = TmpArray[i]->next;
            // PrintArray(TmpArray, k);
            SwapPoint(TmpArray, PreviousPoint, NextPoint, k);
            PreviousPoint = TmpArray[0];
            // PrintList(HeadPoint);
            i = -1;
        }
        i++;
        cnt++;
    } while (TmpPoint != NULL);
    free(TmpArray);
    return HeadPoint;
}

void SwapPoint(LN** TmpArray, LN* PreviousPoint,LN* NextPoint, int step)
{
    int i;
    if (PreviousPoint != NULL)
    {
        PreviousPoint->next = TmpArray[step - 1];
    }
    
    for ( i = step - 1; i >= 1; i--)
    {
        TmpArray[i]->next = TmpArray[i-1];
    }
    TmpArray[i]->next = NextPoint;
}

六、leecode测试结果

暑期编程PK赛 得CSDN机械键盘等精美礼品！