[数据结构与算法]单链表实现每k个元素逆置

?每k个节点头插逆置，下组以当前组逆置后的尾结点为头结点进行头插逆置，依次循环

?

//
// Created by gxj on 2021-08-07.
//设计一个算法每 K 个元素逆置单链表
#include <stdio.h>
#include <stdlib.h>

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode;

//带头结点链表创建
void List_Create(LNode **L){
    (*L) = (LNode*)calloc(1, sizeof(LNode));
    (*L)->next = NULL;
    LNode *r = (*L);//尾指针
    for (int i = 1; i <= 9; ++i) {
        LNode *temp = (LNode*)calloc(1, sizeof(LNode));
        temp->data = i;
        temp->next = r->next;
        r->next = temp;
        r = temp;//尾指针指向新结点
    }
}

//每k个元素用头插法逆置
void reverseKGroup(LNode **L, int k){
    if (k <2 || (*L)->next == NULL)
        return;

    LNode *cur = (*L)->next;//cur工作指针，用于遍历原来整个单链表
    int len = 0;//用于统计单链表中具体节点个数（头结点除外）
    while (cur != NULL) {
        ++len;
        cur = cur->next;
    }

    LNode *p = (*L);//每一组逆置后的尾结点，也是下一组逆置后链表的头结点
    LNode *q = NULL;//用于遍历当前组k个元素链表的工作指针
    LNode *s = NULL;//用于保存每一组逆置前的首结点，也是逆置后的尾结点，在一组逆置转化完后，将其赋值给p，做下组逆置的头结点
    for (int i = 0; i < len/k; ++i) {//总共有几组k元素要反转
        q = p->next;
        s = q;
        p->next = NULL;//断链p结点，将其next指针域初始化，做逆置后的头结点

        for (int j = 0; j < k; ++j) {//一组k个元素就要逆置k次
            cur = q->next;//cur指向原链表当前遍历的元素，为防止断链
            //q头插在p后面
            q->next = p->next;
            p->next = q;
            q = cur;//q指向下一个结点
        }
        p = s;//放回当前组的逆置后的尾结点，用作下组的头结点
        p->next = cur;//p做下组头结点，next指向下组的首结点
    }
}


int main(){
    LNode *L;
    List_Create(&L);//带头结点链表初始化
    reverseKGroup(&L, 3);//每k个元素逆置
    LNode *p = L->next;
    while(p != NULL){
        printf("%d\n", p->data);
        p = p->next;
    }
}

?

?效果如下

?原创码字不易，请勿转载哦，有用的同学欢迎一健三联哦