首页 > 试题广场 >

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

[编程题]链表中的节点每k个一组翻转
  • 热度指数：252329 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。

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

示例1

输入

{1,2,3,4,5},2

输出

{2,1,4,3,5}
示例2

输入

{},1

输出

{}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
C
小洛_头像 小洛_ 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
#include <stdlib.h>
struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    // write code here
    
    //考虑k为0或1以及链表为空、链表长度为1的情况
    if(k < 2 || head == NULL || head->next == NULL)
    {
        return head;
    }
    //思路：每k个节点为一组，每个组逐个翻转(循环嵌套)

    //1.遍历得出链表长度
    int count = 1;//用于记录链表长度
    struct ListNode* pa = head;
    while (pa->next != NULL)
    {
        count++;
        pa = pa->next;
    }

    //2.分组翻转
    //插一个新的首节点，用于锁定翻转后新链表的真正首节点
    struct ListNode *newhead = malloc(sizeof(struct ListNode));
    newhead->next = head;//新节点插在首节点之前，作为暂时的假的首节点
    struct ListNode *pLeft = newhead;
    struct ListNode *pMid = newhead;
    struct ListNode *pRight = NULL;
    //遍历翻转
    for (int i = 0; i < (count / k); i++) {//外循环，i为组号，每k个一组，分组遍历翻转
        pLeft = pMid;
        pMid = pMid->next;
        for (int j = 1; j < k; j++) {//内循环，j为每组中节点序号，每组各自进行翻转
            pRight = pMid->next;
            pMid->next = pRight->next;
            pRight->next = pLeft->next;
            pLeft->next = pRight;
        }
    
    }

    return newhead->next;//返回真正的首节点
}

发表于 2023-11-12 11:04:20 回复(0)
C
harris丨xu头像 harris丨xu 
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @param k int整型
 * @return ListNode类
 */
struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    // write code here
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode *newnode = malloc(sizeof(struct ListNode));
    newnode->next = head;
    struct ListNode *cur = newnode, *prev = newnode;
    struct ListNode *next = NULL;

    //计算链表长度
    int cnt = 1;
    struct ListNode *len = head;
    while (len->next != NULL) {
        cnt++;
        len=len->next;
    }

    for (int i = 0; i < (cnt/k); i++) {
        prev = cur;
        cur = cur->next;

        for (int j = 1; j < k; j++) {
            next = cur->next;
            cur->next = next->next;
            next->next = prev->next;
            prev->next = next;
        }
    }

    return newnode->next;
}

发表于 2023-11-09 15:22:13 回复(0)
C
牛客436686964号头像 牛客436686964号
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    struct ListNode newhead;
    newhead.next = head;
    struct ListNode* cot = &newhead;
    struct ListNode* p = head;
    struct ListNode* p1 = head;
    struct ListNode* p2 = NULL;
    struct ListNode* p3 = cot;
    int n = 0;

    while (p1 != NULL) {
        n++;
        p1 = p1->next;
        if (n % k == 0) {
            for (int i = 1; i < k; i++) {
                struct ListNode* temp = p->next;
                p->next = temp->next;
                temp->next = p3->next;
                p3->next = temp;
            }
            p3 = p;
            p = p->next;
        }
    }

    return newhead.next;
}

发表于 2023-10-28 21:37:52 回复(0)
C
A202302282044461头像 A202302282044461
struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    // write code here
    if(head == NULL || k==1)
        return head;
   
    struct ListNode * pHead = NULL;
    struct ListNode * temp = NULL;
    struct ListNode * cur = NULL;
    struct ListNode * pTail = head;
    int i;

    for (i=0; i<k; i++)
    {
        if(pTail==NULL)
        {
            return head;
        }
        pTail = pTail->next;
    }
    cur = head;//头插法，记录k个节点反转后的最后一个节点
    while (head!=pTail) {
        temp = head;
        head = head->next;
        temp->next = pHead;
        pHead = temp;
    }
    cur->next=reverseKGroup(pTail, k );//连接后面的链表
    return pHead;
}
发表于 2023-08-28 16:55:57 回复(0)
C
问都头像 问都
很low的办法，每到一组一直调用反转指定位置的函数，然后写好结束判断
struct ListNode* reverseBetween(struct ListNode*head, int m, int n) {
    // write code here;
    if ((head)->next == NULL || head == NULL || m == n)
        return head;
    struct ListNode* H = malloc(sizeof(struct ListNode));
    H->next = head;
    struct ListNode* cur, * pre, * tmp;
    cur = H;
    for (int i = 0; i < m - 1; i++) {
        cur = cur->next;
    }
    pre = cur;
    cur = cur->next;
    for (int i = 0; i < n - m; i++) {
        tmp = cur->next;
        cur->next = tmp->next;
        tmp->next = pre->next;
        pre->next = tmp;
    }
    return H->next;
}
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    // write code here

    int n = 0;
    struct ListNode* pnum = head;
    while (pnum) {
        n++; //链表元素个数
        pnum = pnum->next;
    }
    if (head == NULL || head->next == NULL || k == 1 || n < k)
        return head;
    struct ListNode* pn = head;
    int i = 1;
    for (;;)
    {
        pn=reverseBetween(pn , i, i + k - 1);
        i = i + k;
        if (i + k > n || i > n)
            return pn;
    }
}
发表于 2023-08-19 18:57:57 回复(0)
C
想吃开封菜的追梦人在研究求职打法头像 想吃开封菜的追梦人在研究求职打法 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param k int整型 
 * @return ListNode类
 */

 
#include <stdlib.h>
/*
struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    struct ListNode *res=(struct ListNode*)malloc(sizeof(struct ListNode));
    res->next=head;
    if(head==NULL)
    {
        return NULL;
    }
    struct ListNode *pre=res;
    //获得链表长度
    int n=1;
    struct ListNode *length=head;
    while (length->next!=NULL) {
        n++;
        length=length->next;
    }
    for(int i=0;i<(n/k);i++)
    {
        struct ListNode *cur=pre->next;
        for(int j=1;j<k;j++)
        {
            struct ListNode *head1=cur->next;
            cur->next=head1->next;
            head1->next=pre->next;
            pre->next=head1;
        }
        pre=cur;
    }
    return res->next;
}
*/

//sosososososososososo goodgood

struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    struct ListNode *tail=head;//找到每次翻转的尾部!!!!!***
    //遍历k次到尾部
    for(int i=0;i<k;i++)
    {
        if(tail==NULL)
        {
            return head;
        }
        tail=tail->next;
    }

    struct ListNode *pre=NULL;
    struct ListNode *cur=head;
    while (cur!=tail) {
        struct ListNode *head1=cur->next;
        cur->next=pre;
        pre=cur;
        cur=head1;
    }
    head->next=reverseKGroup(tail, k);
    return pre;
}

发表于 2023-08-17 14:24:12 回复(0)
C
E330嵌入式头像 E330嵌入式
struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    struct ListNode dummy;
    dummy.next = head;
    struct ListNode* pre = head;
    int cnt1 = 0;
    while(pre){
            ++cnt1;
            pre = pre->next;
           
    }
    int cnt = cnt1/k;

    struct ListNode* pre1=&dummy;
    struct ListNode* cur = pre1->next;
    struct ListNode* curr = NULL;
    while(cnt){
        for(int j =0; j < k-1;++j){
            curr = cur->next;
            cur->next = curr->next;
            curr->next = pre1->next;
            pre1->next = curr;
        }
        for(int n = 0 ; n < k; ++n){
            pre1 = pre1->next;
        }
        cur = pre1->next;
        --cnt;
    }
    return dummy.next;

}
发表于 2023-07-25 09:52:56 回复(0)
C
Sanming头像 Sanming
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @param k int整型
 * @return ListNode类
 */
struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    // write code here
    struct ListNode* pre = NULL;
    struct ListNode* next = NULL;
    struct ListNode* phead = NULL;  //返回指针
    struct ListNode* p = NULL;

    struct ListNode* pconvhead = NULL;  //记录每次翻转的初始节点指针
    struct ListNode* plastconvhead = NULL;
    int i=0;
    int j=0;
    int length=0;

    //返回的链表头
    phead = head;
    p = head;

    if(head ==NULL||head->next == NULL)
        return head;
    else
     {

        //遍历一遍获得链表长度
        while(p)
        {
            p=p->next;
            length++;
        }
        if(k==1||length/k==0)
            return head;

        plastconvhead = head;

        for(j=0;j<length/k;j++)
        {
            for(i=0;i<k;i++)
            {
                if(i==0)
                    pconvhead = head;
                next = head->next;
                head->next = pre;
                pre = head;
                head = next;
            }

            //记录链表头
            if(j==0)
                phead = pre;

            if(j != 0)
            {
               //上一次反转后的末尾指向下一次翻转完成的起始
                plastconvhead->next = pre;
                plastconvhead = pconvhead;
            }

            pre = NULL;  
            next = NULL;
        }

        pconvhead->next = head;

        return phead;
     }
}
发表于 2023-04-08 11:43:35 回复(0)
C
帅奶哟。头像 帅奶哟。 
struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    // write code here
    struct ListNode *tail = head;
    //1、递归结束的点(k个为一组，不足k个直接返回head)
    for (int i = 0; i < k; i++){
        if (tail == NULL) {
            return head;
        }
        tail = tail->next;
    }

    struct ListNode *pre = NULL;
    struct ListNode *cur = head;
    struct ListNode *nex;
    //2、每一级的任务
    while (cur != tail) {
        nex = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nex;
    }
    head->next = reverseKGroup(tail, k);
    //3、找到返回值
    return pre;
}

发表于 2023-03-19 14:50:13 回复(0)
C
我要搞钱呀头像 我要搞钱呀
有什么问题吗？为什么程序会发生段错误啊

//反转链表函数
#include <stdio.h>
struct ListNode* reverse(struct ListNode* head, struct ListNode *tail){
    if(head == NULL || head->next == NULL){
        return head;
    }

    struct ListNode *cur = head;
    struct ListNode *pre = NULL;
    struct ListNode *next = cur->next;
    while(cur != tail){
        next = cur->next;
        cur->next = pre;
        pre->next = cur;
        cur = next;
    }
    return pre;
}

struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    // write code here
    struct ListNode *node = head;
    for(int i = 0; i < k; i++){
        if(node == NULL){
            return head;
        }
        node = node->next;
    }

    struct ListNode *res = reverse(head, node);
    head->next = reverseKGroup(node, k);
    return res;
}
发表于 2023-03-06 17:09:03 回复(0)
C
JayneChou头像 JayneChou 
#include <stdlib.h>
struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    struct ListNode* phead = (struct ListNode*)malloc(sizeof(struct ListNode));
    phead->next = head;
    struct ListNode *prior = head, *rear = head, *cur = head, *temp = cur;
    for(int i = 0; i < k - 1 && rear; i++){
        rear = rear->next;
    }
    if(!rear || k == 1){
        return head;
    } else {
        struct ListNode *cur_following = head->next;
        //phead指向第一轮最后一个元素
        phead->next = rear;
        while(rear){
            rear = rear->next;//rear位于第k+1个位置
            for (int i = 0; i < k - 1; i++) {
                //反转
                temp = cur_following;
                cur_following =cur_following->next;
                temp->next = cur;
                cur = temp;
                if(rear){
                    rear = rear->next;
                }
            }
            if(rear){
                //还有下一轮反转，则上一轮第一个节点指针域改为下一轮最后一个元素，
                // 否则改为下一轮第一个元素,也就是一轮循环后cur_following的位置
                prior->next = rear;
                prior = cur_following;
                //如果说还有下一轮还需要反转，则cur需要跟第一轮一样移动到下一轮第一个位置上，
                // 保持跟第一轮反转之前的状态一样，否则下面一轮第一个元素也被反转了，指针域连到上一轮最后一个。
                cur = cur_following;
                cur_following = cur_following->next;
            } else {
                prior->next = cur_following;
            }
        }
        return phead->next;
    }
}

发表于 2023-02-17 17:52:50 回复(0)
C
会飞的芜香蛋头像 会飞的芜香蛋 
struct ListNode* reverseKGroup(struct ListNode* head, int k ){
    if(k == 1)//每一个一组等于不逆置
        return head;
    if(!head)//是否为空表
        return head;
    struct ListNode* low = head;
    struct ListNode* high = head;
    struct ListNode* plow = NULL;
    struct ListNode* lhigh = NULL;
    struct ListNode* p = NULL;
    struct ListNode* q = NULL;
    struct ListNode* tlow = NULL;
    int i = 0, n = 0;//i用来判断未逆置链表中是否有连续k个节点，n判断是否是第一次逆置
    for(i = 1; i <= k && high; i++){
        if(i == k){
            i = 1;
            n++;
            tlow = low;
            lhigh = high->next;
            p = low->next;
            q = p->next;
            low->next = NULL;//摘头节点逆置法
            while(p != lhigh){
                p->next = tlow;
                tlow = p;
                p = q;
                if(q)
                    q = p->next;
            }//逆置
            if(n == 1){
                plow = head;
                head = high;
            }//判断是否是第一次逆置
            else
                plow->next = high;
            low->next = lhigh;
            plow = low;
            high = p;
            low = p;
        }
        if(high)
            high=high->next;//写for里会导致溢出
    }
    return head;
}

发表于 2023-02-05 17:29:38 回复(0)
C
lijd头像 lijd 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
#include <stdio.h>

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    // write code here
    if(head == NULL || head->next == NULL || k == 1) {
        return  head;
    }
    int iNodeNums = 0;
    struct ListNode* pHead = NULL, *pTail = NULL, *ptr1 = head;

    while (ptr1) {
        iNodeNums++; ptr1 = ptr1->next;
    }
    
    iNodeNums /= k;

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

    ptr1 = head;
    while(iNodeNums--){
        struct ListNode* ptr2 = ptr1, *ptr3 = NULL, *ptr4 = NULL;
        int i = k;
        while (i-- && ptr2) {
            printf("i:%d, head : %d\n", i, ptr2->val);
            ptr3 = ptr2->next;
            ptr2->next = ptr4;
            ptr4 = ptr2;
            ptr2 = ptr3;
        }

        if (pHead) {
            pTail->next = ptr4;
        }else {
            pHead = ptr4;
        }
        pTail = ptr1;

        ptr1 = ptr3;
    }

    if (ptr1) {
        pTail->next = ptr1;
    }
    
    return  pHead;
}

发表于 2023-01-16 15:58:12 回复(0)
C
admin_guo头像 admin_guo 
struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    // write code here
    if (head == NULL)
        return NULL;
    if (head->next == NULL || k == 1)
        return head;
    typedef struct ListNode Node;
    Node top;
    top.val = 0;
    top.next = head;
    Node *res = &top;
    Node *pre = res;
    Node *cur = res->next;
    int sum = 0, flag = 0, index = 1;
    while (head != NULL) {
        sum++;
        head = head->next;
    }
    flag = sum / k;
    while (cur->next != NULL) {
        if (!flag) 
            break;
        if (index < k) {
            Node *temp = cur->next;
            cur->next = temp->next;
            temp->next = pre->next;
            pre->next = temp;
            index++;
        }else {
            pre = cur;
            cur = cur->next;
            index = 1;
            flag--;
        }
    }
    return res->next;
}

发表于 2022-12-15 17:15:37 回复(0)
C
_Herc头像 _Herc

struct ListNode* reverse(struct ListNode* head, int k){
    struct ListNode *cur, *next, *pre;
    pre = NULL, cur = head, next = head->next;
    while(k--){
        cur->next = pre;
        pre = cur;
        cur = next;
        next = next->next;
    }
    return pre;
}

struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    // write code here
    struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummyHead->next = head;
    struct ListNode* revHead, *revEnd;
    int count = 0;
    revHead = dummyHead, revEnd = dummyHead->next;  //head表示反转区间前一个节点，end表示反转区间后一个节点

    if(k == 1)                  //如果k=1，则直接返回
        return dummyHead->next;

    while(revEnd){              //寻找区间节点过程中，如果区间后的节点不存在，则直接退出
        revEnd = revEnd->next;  //存在则指向下一个
        if(++count == k){       //如果找到一个满足k的区间，则开始反转
            revHead->next = reverse(revHead->next, k); //区间前一个节点的next  为  反转后链表
            while(count--){     //找到反转后的链表的 区间的末尾节点
                revHead = revHead->next;
            }
            revHead->next = revEnd; //此时head为反转好的区间的末尾节点，next指向之前保存的反转区间的后一个节点，
            //同时revHead处于下一区间的前一个节点。[2 1(head)] [3 4]
            count = 0;            //count置0
        }
    }
    return dummyHead->next;
}
发表于 2022-11-01 11:26:25 回复(0)
提交观点

问题信息

链表
难度：
30条回答 25339浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号