c语言链表中的节点每k个一组翻转

1.问题描述

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。

数据范围： ， ，链表中每个元素都满足
要求空间复杂度 ，时间复杂度
例如：
给定的链表是
对于 , 你应该返回
对于 , 你应该返回

2.源码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

typedef struct ListNode ListNode;

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

void ListPush(ListNode **head, int val)
{
    ListNode *pre = NULL;
    ListNode *cur = (*head);

    if(cur == NULL)
    {
        *head = (ListNode *)malloc(sizeof(ListNode));

        (*head)->val = val;
        (*head)->next = NULL;

        return;
    }

    while(cur)
    {
        pre = cur;
        cur = cur->next;
    }

    cur = (ListNode *)malloc(sizeof(ListNode));

    pre->next = cur;
    cur->val = val;
    cur->next = NULL;

    return;
}

void ListFree(ListNode **head)
{
    ListNode *next = NULL;
    ListNode *cur = (*head);

    while(cur)
    {
        next = cur->next;

        free(cur);

        cur = next;
    }

    *head = NULL;
}

void ListPrint(ListNode *head)
{
    ListNode *cur = head;

    while(cur)
    {
        printf("%d ", cur->val);

        cur = cur->next;
    }

    printf("\n");
}

struct ListNode *reverseKGroup(struct ListNode *head, int k)
{
    struct ListNode *pre = NULL;
    struct ListNode *cur = head;
    struct ListNode *next = NULL;
    struct ListNode *t[2] = {NULL, NULL};
    int len = 0;
    int u = 0;
    int i;

    if(head == NULL)
    {
        return head;
    }

    if(k == 1)
    {
        return head;
    }

    while(cur)
    {
        cur = cur->next;
        len++;
    }

    u = len / k;

    if(u == 0)
    {
        return head;
    }

    pre = NULL;
    cur = head;

    for(i=0; i<k; i++)
    {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }

    head->next = cur;

    t[0] = pre;
    pre = head;
    head = t[0];

    t[0] = pre;

    u--;

    while(u)
    {
        for(i=0; i<k; i++)
        {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }

        t[1] = t[0]->next;

        if(t[0]->next)
        {
            t[0]->next->next = cur;
        }

        t[0]->next = pre;
        pre = t[1];

        t[0] = pre;

        u--;
    }

    return head;
}

int main()
{
    ListNode *head = NULL;

    ListPush(&head, 1);
    ListPush(&head, 2);
    ListPush(&head, 3);
    ListPush(&head, 4);
    ListPush(&head, 5);
    ListPush(&head, 6);

    ListPrint(head);

    head = reverseKGroup(head, 3);

    ListPrint(head);

    ListFree(&head);

    return 0;
}

3.编译源码

$ gcc -o test  test.c -std=c89

4.运行及其结果

$ ./test
1 2 3 4 5 6
3 2 1 6 5 4