K个一组翻转链表

编辑:谯胜平      分类:程序与算法      标签:反转链表      发布时间:2021-04-14      浏览次数:701

1、题目描述:

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

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]

提示:

列表中节点的数量在范围 sz 内

1 <= sz <= 5000

0 <= Node.val <= 1000

1 <= k <= sz

2、解题思路

采用递归方式进行解题,先求当前链表长度len;

①如果len < k,返回head;

②如果len >= k,反转链表的前k个节点得子链表1,递归反转剩下的len-k个节点得链表2,返回链表1和链表2连接之后的链表;

3、AC代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *q = head;
        //求链表长度,当长度大于等于k时即可跳出循环
        int len = 0;
        while(q != nullptr && len < k){
            len++;
            q = q -> next;
        }
        if(len < k){        //长度小于k,直接返回head
            return head;
        }else{
            //将链表的前k个节点进行反转
            ListNode *q = head, *newHead = nullptr;
            for(int i = 0; i < k; i++){
                ListNode *temp = newHead;
                newHead = q;
                q = q -> next;
                newHead -> next = temp;
            }
            //head节点是反转之后的最后一个节点,将其连接上递归翻转的len-k个节点
            head -> next = reverseKGroup(q, k);
            return newHead; 
        }
    }
};


看不清?换一个