25. K 个一组翻转链表

简介: 25. K 个一组翻转链表

题目描述

给你链表的头节点 head ,每 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]

提示:

  • 链表中的节点数目为 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

进阶:你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗?

解题思路

此题目可以看作第24题的升级版本。在第24中,k=2。

那么该题的思路也是很简单的。直接递归,然后把递归好的链表接到原来的链表上面。

注意依次是从后往前。(代码的整体逻辑基本和力扣第24题一样)

代码

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(k==1) return head;

        ListNode* nodeHead=head;
        for(int i=0;i<k;i++)
        {
            if(nodeHead==nullptr) return head;
            nodeHead=nodeHead->next;
        } 
        nodeHead=reverseKGroup(nodeHead,k);

        ListNode* cur=head;
        ListNode* next=head->next;
        ListNode* ret=cur;
        for(int i=0;i<k;i++)
        {
            ret=cur;
            cur->next=nodeHead;
            nodeHead=cur;
            cur=next;
            //注意可能为空
            if(next)
                next=next->next;
        }

        return ret;
    }
};
相关文章
【 腾讯精选练习 50 题】01—翻转链表
【 腾讯精选练习 50 题】01—翻转链表
|
1天前
25. K个一组翻转链表
25. K个一组翻转链表
|
6天前
|
算法 数据挖掘 Python
LeetCode题目25 hard:K个一组翻转链表 【分治策略 Python】
LeetCode题目25 hard:K个一组翻转链表 【分治策略 Python】
|
9天前
|
算法
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
8 0
|
10天前
|
算法 Java C语言
【经典算法】LeetCode25:K 个一组翻转链表(Java/C/Python3,Hard)
【经典算法】LeetCode25:K 个一组翻转链表(Java/C/Python3,Hard)
5 1
|
1月前
|
算法 Java Go
Golang每日一练(leetDay0098) 生命、Nim、猜数字游戏
Golang每日一练(leetDay0098) 生命、Nim、猜数字游戏
30 0
Golang每日一练(leetDay0098) 生命、Nim、猜数字游戏
|
1月前
|
Java Go 人工智能
Java每日一练(20230502) BST公共祖先、随机分组、K个一组翻转链表
Java每日一练(20230502) BST公共祖先、随机分组、K个一组翻转链表
29 0
Java每日一练(20230502) BST公共祖先、随机分组、K个一组翻转链表
|
1月前
|
Python Java Go
Python每日一练(20230430) 移除元素、删除排序链表中的重复元素、搜索旋转排序数组II
Python每日一练(20230430) 移除元素、删除排序链表中的重复元素、搜索旋转排序数组II
56 0
Python每日一练(20230430) 移除元素、删除排序链表中的重复元素、搜索旋转排序数组II
|
1月前
leetcode-25:K 个一组翻转链表
leetcode-25:K 个一组翻转链表
20 0
|
5天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表