你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

k个一组翻转链表(力扣题目 C语言解法)

2021/12/26 17:16:17

目录

图示:

 代码:


给你一个链表,每 个节点一组进行翻转,请你返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

示例 1:

输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]

示例 2:

输入:head = [1,2,3,4,5], k = 3
输出:[3,2,1,4,5]

示例 3:

输入:head = [1,2,3,4,5], k = 1
输出:[1,2,3,4,5]

示例 4:

输入:head = [1], k = 1
输出:[1]

 以上是力扣上的一道K个一组翻转单链表的题目。我的解题思路如下:

第一步:算出链表有几个节点,用总节点个数除以k,算出一共要翻转几组。

第二步:把链表每k个一组进行翻转,然后把翻转后的单独的一组拆下来依次尾插到给定的(自己定义的)头节点之后。

第三步:把没有翻转的最后一部分链接在最后。

图示:

初始时的链表:

第一次翻转拼接后:

 

第二次翻转拼接后:

第三次拼接:

 代码:

struct ListNode* reverseKGroup(struct ListNode* head, int k){
    int x=k;
    int count=0;//算出链表有多少个节点
    struct ListNode s;//给出一个头节点,方便进行插入
    struct ListNode* cur=&s;//指向给出的头节点
    struct ListNode* slow=head;
    struct ListNode* fast=NULL;
    struct ListNode* prev=NULL;
    while(slow){
        count++;
        slow=slow->next;
    }
    slow=head;
    count/=k;//算出到底要进行几次翻转
    for(int i=0;i<count;i++){
        while(x){//进行翻转
            fast=slow->next;
            slow->next=prev;
            prev=slow;
            slow=fast;
            x--;
        }
        cur->next=prev;
        while(cur->next){//cur向前走,为下一次拼接做准备
            cur=cur->next;
        }
        prev=NULL;//必须置空,保证下一次cur向前走不会死循环
        x=k;
    }
    cur->next=slow;//最后链接没有被翻转的部分
    return s.next;
}

 注意:先要了解翻转链表的方法,然后这道题目就容易了。