【算法】力扣:K个一组反转链表
前置知识
- 数据结构-链表
- 反转部分链表
- 算法题的手写栈使用
难度:
- 初阶:使用容器, 难度中等。
- 进阶:纯coding修改指针 ,难度中等,虽然leetcode是困难题。不过更加注重细节。
题目:反转 k 组中的节点
给定一个单链表的头节点head, 实现一个调整单链表的函数, 要求每k个节点之间逆序, 如果不够k个节点,那么不调整。
输入: head = [1,2,3,4,5], k = 2
输出: [2,1,4,3,5]
其中, [1,2]为一组,[3,4]为一组,5不足则不调整。
[1,2]逆序[2,1], [3,4]逆序[4,3]。
细节处理:
- 第一组逆转时, 整个链表的头节点从原来的1改成了2, 涉及
换头逻辑处理。 题目也要求返回新链表的头节点。需要处理。 1 <= k <= n <= 5000, 力扣给定范围。考虑特殊数据的处理。 k<2的链表是不需要处理的。因为k<=0视为无效,k==1是对单个节点进行逆序,没有意义。因此,排除了1的处理。- 由于我们逆序的是某个链表的局部, 这就涉及对整体链表与局部修改连接的维护。具体看code。
解法1:使用栈这个容器
事先声明, 这里采用的是全局静态数组充当栈的写法, 读者可根据需求自行改写成Java,C++内置栈的写法。
讲解在代码下面。
//提交代码, 将类名ReverseGroup -> Solution
public class ReverseGroup {//题目给定k最大5000,那么5001肯定足够了。 实测1201也可以public static int MAX = 5001;//类静态数组充当栈public static ListNode[] stack = new ListNode[MAX];//记录栈的大小, size == 0意味栈空。public static int size;//主方法public ListNode reverseKGroup(ListNode head, int k) {//排除无效数据if(k < 2) {return head;}//重置size,防止被上组数据污染, 实现空间复用。size = 0;return f(head,k);//调用辅助方法}/*** * @param head 原链表头节点* @param k 每k个逆序* @return 返回新链表的头节点*/private ListNode f(ListNode head, int k) {ListNode newHead = head, cur = head, prev = null, next = null;while(cur != null) {next = cur.next;//压栈stack[size++] = cur;while(size==k) {//满足则执行逆序prev = reversePart(prev,next);//调整newHead为修改后链表的头节点。newHead = newHead == head?cur: newHead;}cur = next;}return newHead;}/*** * @param left 修改局部链表头节点的前驱* @param right 修改局部链表尾节点的后继* @return 返回下一对修改局部链表的前驱节点。*/private ListNode reversePart(ListNode left, ListNode right) {ListNode cur = stack[--size];if(left != null) {left.next = cur;}ListNode next = null;while(size > 0) {next = stack[--size];cur.next = next;cur = next;}cur.next = right;return cur;}
}
private ListNode f(ListNode head, int k) {ListNode newHead = head, cur = head, prev = null, next = null;while(cur != null) {next = cur.next;//压栈stack[size++] = cur;while(size==k) {//满足则执行逆序prev = reversePart(prev,next);//调整newHead为修改后链表的头节点。newHead = newHead == head?cur: newHead;}cur = next;}return newHead;}
newHead:修改后链表的新头节点。从逻辑上有两种可能, 如果发生第一组的调整, 那么newHead一定不是原先的head, 那么你可以看到内层while循环内部newHead = newHead == head?cur: newHead;, 就是第一组逆序, newHead应该指向cur的节点。
比如,[1,2,3,4,5], k=2, cur在应该指向2这个节点,刚好第一组逆序[2,1,3,4,5], cur指向节点就是修改后的新头节点。cur指向的就是当前要入栈的节点,压栈 stack[size++] = cur;cur还充当外部循环遍历链表的作用。next: 修改局部链表尾节点的后继, 当发生逆序过程时,next指向那一组尾节点的后继。比如[1,2]逆序时,next指向2的后继3。因为只有进入循环, next始终是cur.next。prev:修改局部链表头节点的前驱, 第一组修改时为null,所以初始化为null,后续组的前驱节点交给reversePart函数返回值维护。size==k,当前栈大小满足k时需要逆序这组。reversePart(prev,next)这个函数,接受这组的前驱和后继,比如[1,2,3,4,5], k=2, 先逆序[1,2],就需要传入null前驱,3后继。因为函数内部逻辑要维护局部修改和整体的连接。reversePart(prev,next),这个函数还需要返回下一组(如果不存在那么用不上了)的前驱节点。比如[2,1,3,4,5]完成了1,2之间的逆序,那么还要返回下一对[3,4]的前驱1。那么下一次调用就传入1前驱和5后继来逆序3,4。
private ListNode reversePart(ListNode left, ListNode right) {ListNode cur = stack[--size];if(left != null) {left.next = cur;}ListNode next = null;while(size > 0) {next = stack[--size];cur.next = next;cur = next;}cur.next = right;return cur;}
- 先出栈, 出栈节点就是局部链表的头结点, left(不为空)连接该节点。
- 循环出栈连接逻辑
- 最后出栈的结点连接后继right。
- 返回下一组的前驱节点就是当前cur的节点。自行画图理解。

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( k ) O(k) O(k)
解法2:原链表调整
//提交时,注意修改函数名public ListNode reverseKGroup1(ListNode head, int k) {// 特殊输入判断if (k < 2) {return head;}ListNode cur = head, start = null, prev = null, next = null;int count = 1;// 计数变量。while (cur != null) {next = cur.next;// 后继始终跟着循环更新。if (count == k) {start = prev == null ? head : prev.next;// 获得当前逆序对开始节点head = prev == null ? cur : head;// 第一组逆序需要修改头节点reversePart2(prev, start, cur, next);// (prev,next),[start,end]prev = start;// 更新前驱范围count = 0;// 重置}++count;// 自增cur = next;// cur跟着next。}return head;// head指向的更新后的头节点或者原先的头节点。}private void reversePart2(ListNode left, ListNode start, ListNode end,ListNode right) {//反转部分链表一样的逻辑 ListNode prev = start,next = null, cur = start.next;while(cur != right){next = cur.next;cur.next = prev;prev = cur;cur = next;}if(left!=null) {left.next = end;}start.next = right;}

每日两题结束。
相关文章:
【算法】力扣:K个一组反转链表
前置知识 数据结构-链表反转部分链表算法题的手写栈使用 难度: 初阶:使用容器, 难度中等。进阶:纯coding修改指针 ,难度中等,虽然leetcode是困难题。不过更加注重细节。 题目:反转 k 组中的…...
Matlab报错——错误使用 vertcat
错误提示: 原因: 这个错误表明 segment_lengths 的维度和 0 不一致。在 MATLAB 中,有时,diff 函数的输出可能是行向量,而segment_lengths 应该是一个列向量才能与 0 正确连接。 解决方法: 使用转置操作 …...
【如何获取股票数据10】Python、Java等多种主流语言实例演示获取股票行情api接口之沪深A股历史分时KDJ数据获取实例演示及接口API说明文档
最近一两年内,股票量化分析逐渐成为热门话题。而从事这一领域工作的第一步,就是获取全面且准确的股票数据。因为无论是实时交易数据、历史交易记录、财务数据还是基本面信息,这些数据都是我们进行量化分析时不可或缺的宝贵资源。我们的主要任…...
进入 Searing-66 火焰星球:第一周游戏指南
Alpha 第四季已开启,穿越火焰星球 Searing-66,带你开启火热征程。准备好勇闯炙热的沙漠,那里有无情的高温和无情的挑战在等待着你。从高风险的烹饪对决到炙热的冒险,Searing-66 将把你的耐力推向极限。带上充足的水,天…...
考研论坛设计小程序ssm+论文源码调试讲解
2相关技术 2.1微信小程序 小程序是一种新的开放能力,开发者可以快速地开发一个小程序。小程序可以在微信内被便捷地获取和传播,同时具有出色的使用体验。尤其拥抱微信生态圈,让微信小程序更加的如虎添翼,发展迅猛。 2.2 MYSQL数据…...
JAVA笔记 | EasyExcel创建带有简单下拉框的导入模板
目录 前文 业务需求 具体代码 新增Handler 控制层 前文 SpringBoot笔记 | EasyExcel导入导出及基于模板导出_easyexcel模板导出-CSDN博客 业务需求 需要一个导出模板。一个列需要填写固定的值,或者方便用户填写。 自己需求,几个固定的字段对应固…...
【含开题报告+文档+PPT+源码】贫困儿童一对一扶贫帮扶系统设计与实现
开题报告 根据《中华人民共和国慈善法》第五十八条规定,慈善组织确定慈善受益人,应当坚持公开、公平、公正的原则,不得指定慈善组织管理人员的利害关系人作为受益人[2]。以上所列举的平台基本没有做到公开、公平、公正的原则,例如…...
多系统萎缩不慌张,这些维生素是你的“隐形盾牌”!️
在这个快节奏的时代,健康成为了我们最宝贵的财富。而对于多系统萎缩(MSA)的患者来说,合理的营养补充更是维护身体机能、提升生活质量的关键一步。今天,就让我们一起揭秘那些能够成为多系统萎缩患者“守护神”的维生素吧…...
IGFBP7:免疫治疗新靶点
前 言 胰岛素样生长因子结合蛋白7(IGFBP7)是胰岛素超家族的生长促进肽成员,可与胰岛素和IGF结合,调控细胞生长和分化。IGFBP7在不同的肿瘤类型中表现出抑制或促进肿瘤生长的“自相矛盾”活性。研究发现IGFBP7可增强治疗性单克隆…...
深度学习模型的架构与应用:技术解析与未来展望
1. 引言 深度学习(Deep Learning)模型是当代人工智能的核心技术之一,广泛应用于语音识别、计算机视觉、自然语言处理、推荐系统等众多领域。深度学习通过构建多层神经网络,能够自动从大规模数据中学习复杂的特征和模式,其应用成果不仅推动了技术的飞跃,也带来了智能化产…...
机器学习——主要分类
前言: 机器学习是人工智能的重要分支之一,它通过分析数据来构建模型,并通过这些模型进行预测、分类或决策。随着数据量的迅速增长,机器学习在多个领域展现出巨大的应用潜力,推动了科技的进步。根据学习方式和数据的使用…...
Java密封类(Sealed Classes)增强详解
Java密封类(Sealed Classes)增强详解 Java 17引入了一个重要的新特性——密封类(Sealed Classes),这一特性旨在增强Java编程语言的能力,提供了一种机制来限制哪些类可以继承一个给定的类或者实现一个给定的…...
鸿蒙如何自动生成二维码?QRCode组件
QRCode 用于显示单个二维码的组件。 说明: 该组件从API Version 7开始支持。后续版本如有新增内容,则采用上角标单独标记该内容的起始版本。 二维码组件的像素点数量与内容有关,当组件尺寸过小时,可能出现无法展示内容的情况&…...
【分布式知识】MapReduce详细介绍
文章目录 MapReduce概述1. MapReduce编程模型Map阶段Reduce阶段 2. Shuffle和Sort阶段3. MapReduce作业的执行流程4. MapReduce的优化和特性5. MapReduce的配置和调优 MapReduce局限性相关文献 MapReduce概述 MapReduce是一个分布式计算框架,它允许用户编写可以在大…...
JAVA八股
快速失败(fail-fast) 设计的目的是为了避免在遍历时对集合进行并发修改,从而引发潜在的不可预料的错误。 通过迭代器遍历集合时修改集合: 如果你使用Iterator遍历集合,然后直接使用集合的修改方法(如add(…...
关于武汉芯景科技有限公司的限流开关芯片XJ6288开发指南(兼容SY6288)
一、芯片引脚介绍 1.芯片引脚 二、系统结构图 三、功能描述 1.EN引脚控制IN和OUT引脚的通断 2.OCB引脚指示状态 3.过流自动断开...
指令:计算机的语言(五)
2.9 人机交互 ASCII与二进制 对应表略 字节转移指令 lbu:加载无符号字节,从内存中加载1个字节,放在寄存器最右边8位。 sb:存储字节指令,从寄存器的最右边取1个字节并将其写入内存。 复制1个字节顺序如下…...
C#笔记(1)
解决方案: 【1】组织项目:把项目放在放在一个解决方案中,统一开发,统一编译。 【2】管理项目:开发中的任何问题,在统一编译过程中,都能随时发现。也可以添加第三方的库文件。 命名空间: 命名空…...
SSDF攻击、防御与展望
摘要: 随着无线通信业务的不断发展,频域也越来越成为了一种珍贵的稀缺资源,与此同时,相应的无线电安全问题层出不穷,为无线通信造成了十分恶劣的影响,本文从深入理解认知无线电安全开始,对一些典…...
MedMamba代码解释及用于糖尿病视网膜病变分类
MedMamba原理和用于糖尿病视网膜病变检测尝试 1.MedMamba原理 MedMamba发表于2024.9.28,是构建在Vision Mamba基础之上,融合了卷积神经网的架构,结构如下图: 原理简述就是图片输入后按通道输入后切分为两部分,一部分走…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
