链表中节点每k 个一组翻转_c 语言编程 给你一个链表,每k个节点一组进行翻转 csdn

题目：

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
要求空间复杂度 O(1)

例如：

给定的链表是1→2→3→4→5

对于 k=2, 你应该返回 2→1→4→3→5

对于 k=3, 你应该返回 3→2→1→4→5

 

思路分析：

链表需要每k个就翻转一次，那需要用到两个函数进行两次操作：

• 一个是用来对链表进行分段，并确定最后一次是否满足k个节点；
• 一个是用来最小段链表进行翻转，并将新的小段链表头返回；

两个操作可以分别用两个函数封装，也可以放到一个函数中。

 

方法一：可以先统计链表的长度，然后根据长度进行分段，再调用翻转的功能

方法二：通过递归的方法，head记录小段的头，cur记录下一个小段的起点，或是结束点的下一个节点。

 

因为翻转的函数都一样的，这里只提供方法二的代码：

#include <stdio.h>
#include <stdlib.h>
 
typedef struct node
{
    int          value;
    struct node* next;
} list_node;
 
 
 
list_node* reverse(list_node* head, list_node* tail)
{
    list_node* pre  = NULL;
    list_node* next = NULL;
 
    while (head != tail) {
        next       = head->next;
        head->next = pre;
        pre        = head;
        head       = next;
    }
 
    return pre;
}
 
list_node* reverse_k_group(list_node* head, int k)
{
    list_node* cur      = head;
    list_node* new_head = NULL;
 
    for (int i = 0; i < k; ++i) {
        if (!cur) {
            return head;
        }
 
        cur = cur->next;
    }
 
    new_head   = reverse(head, cur);
    head->next = reverse_k_group(cur, k);
 
    return new_head;
}
 
void print(list_node* head, int k)
{
    list_node* cur = head;
 
    while (cur) {
        if (cur != head) {
            printf("->");
        } else {
            printf("k = %d:  ", k);
        }
        printf("%d", cur->value);
 
        cur = cur->next;
    }
    printf("\n");
}
 
void test10()
{
    list_node* head = NULL;
    list_node* cur  = NULL;
 
    for (int i = 0; i < 5; ++i) {
        list_node* node = (list_node*)malloc(sizeof(list_node));
        node->value     = i + 1;
        node->next      = NULL;
 
        if (!head) {
            head = node;
        }
 
        if (!cur) {
            cur = node;
        }
        else {
            cur->next = node;
            cur       = node;
        }
    }
 
    print(head, 1);
 
    head = reverse_k_group(head, 2);
    print(head, 2);
}

 

运行结果：