当前位置: 首页 > news >正文

【算法】力扣: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. 第一组逆转时, 整个链表的头节点从原来的1改成了2, 涉及换头逻辑处理。 题目也要求返回新链表的头节点。需要处理。
  2. 1 <= k <= n <= 5000, 力扣给定范围。考虑特殊数据的处理。 k<2的链表是不需要处理的。因为k<=0视为无效,k==1是对单个节点进行逆序,没有意义。因此,排除了1的处理。
  3. 由于我们逆序的是某个链表的局部, 这就涉及对整体链表与局部修改连接的维护。具体看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;}
  1. 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指向节点就是修改后的新头节点。
  2. cur指向的就是当前要入栈的节点,压栈 stack[size++] = cur;cur还充当外部循环遍历链表的作用。
  3. next: 修改局部链表尾节点的后继, 当发生逆序过程时,next指向那一组尾节点的后继。比如[1,2]逆序时,next指向2的后继3。因为只有进入循环, next始终是cur.next。
  4. prev:修改局部链表头节点的前驱, 第一组修改时为null,所以初始化为null,后续组的前驱节点交给reversePart函数返回值维护。
  5. 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个一组反转链表

前置知识 数据结构-链表反转部分链表算法题的手写栈使用 难度&#xff1a; 初阶&#xff1a;使用容器&#xff0c; 难度中等。进阶&#xff1a;纯coding修改指针 &#xff0c;难度中等&#xff0c;虽然leetcode是困难题。不过更加注重细节。 题目&#xff1a;反转 k 组中的…...

Matlab报错——错误使用 vertcat

错误提示&#xff1a; 原因&#xff1a; 这个错误表明 segment_lengths 的维度和 0 不一致。在 MATLAB 中&#xff0c;有时&#xff0c;diff 函数的输出可能是行向量&#xff0c;而segment_lengths 应该是一个列向量才能与 0 正确连接。 解决方法&#xff1a; 使用转置操作 …...

【如何获取股票数据10】Python、Java等多种主流语言实例演示获取股票行情api接口之沪深A股历史分时KDJ数据获取实例演示及接口API说明文档

最近一两年内&#xff0c;股票量化分析逐渐成为热门话题。而从事这一领域工作的第一步&#xff0c;就是获取全面且准确的股票数据。因为无论是实时交易数据、历史交易记录、财务数据还是基本面信息&#xff0c;这些数据都是我们进行量化分析时不可或缺的宝贵资源。我们的主要任…...

进入 Searing-66 火焰星球:第一周游戏指南

Alpha 第四季已开启&#xff0c;穿越火焰星球 Searing-66&#xff0c;带你开启火热征程。准备好勇闯炙热的沙漠&#xff0c;那里有无情的高温和无情的挑战在等待着你。从高风险的烹饪对决到炙热的冒险&#xff0c;Searing-66 将把你的耐力推向极限。带上充足的水&#xff0c;天…...

考研论坛设计小程序ssm+论文源码调试讲解

2相关技术 2.1微信小程序 小程序是一种新的开放能力&#xff0c;开发者可以快速地开发一个小程序。小程序可以在微信内被便捷地获取和传播&#xff0c;同时具有出色的使用体验。尤其拥抱微信生态圈&#xff0c;让微信小程序更加的如虎添翼&#xff0c;发展迅猛。 2.2 MYSQL数据…...

JAVA笔记 | EasyExcel创建带有简单下拉框的导入模板

目录 前文 业务需求 具体代码 新增Handler 控制层 前文 SpringBoot笔记 | EasyExcel导入导出及基于模板导出_easyexcel模板导出-CSDN博客 业务需求 需要一个导出模板。一个列需要填写固定的值&#xff0c;或者方便用户填写。 自己需求&#xff0c;几个固定的字段对应固…...

【含开题报告+文档+PPT+源码】贫困儿童一对一扶贫帮扶系统设计与实现

开题报告 根据《中华人民共和国慈善法》第五十八条规定&#xff0c;慈善组织确定慈善受益人&#xff0c;应当坚持公开、公平、公正的原则&#xff0c;不得指定慈善组织管理人员的利害关系人作为受益人[2]。以上所列举的平台基本没有做到公开、公平、公正的原则&#xff0c;例如…...

多系统萎缩不慌张,这些维生素是你的“隐形盾牌”!️

在这个快节奏的时代&#xff0c;健康成为了我们最宝贵的财富。而对于多系统萎缩&#xff08;MSA&#xff09;的患者来说&#xff0c;合理的营养补充更是维护身体机能、提升生活质量的关键一步。今天&#xff0c;就让我们一起揭秘那些能够成为多系统萎缩患者“守护神”的维生素吧…...

IGFBP7:免疫治疗新靶点

前 言 胰岛素样生长因子结合蛋白7&#xff08;IGFBP7&#xff09;是胰岛素超家族的生长促进肽成员&#xff0c;可与胰岛素和IGF结合&#xff0c;调控细胞生长和分化。IGFBP7在不同的肿瘤类型中表现出抑制或促进肿瘤生长的“自相矛盾”活性。研究发现IGFBP7可增强治疗性单克隆…...

深度学习模型的架构与应用:技术解析与未来展望

1. 引言 深度学习(Deep Learning)模型是当代人工智能的核心技术之一,广泛应用于语音识别、计算机视觉、自然语言处理、推荐系统等众多领域。深度学习通过构建多层神经网络,能够自动从大规模数据中学习复杂的特征和模式,其应用成果不仅推动了技术的飞跃,也带来了智能化产…...

机器学习——主要分类

前言&#xff1a; 机器学习是人工智能的重要分支之一&#xff0c;它通过分析数据来构建模型&#xff0c;并通过这些模型进行预测、分类或决策。随着数据量的迅速增长&#xff0c;机器学习在多个领域展现出巨大的应用潜力&#xff0c;推动了科技的进步。根据学习方式和数据的使用…...

Java密封类(Sealed Classes)增强详解

Java密封类&#xff08;Sealed Classes&#xff09;增强详解 Java 17引入了一个重要的新特性——密封类&#xff08;Sealed Classes&#xff09;&#xff0c;这一特性旨在增强Java编程语言的能力&#xff0c;提供了一种机制来限制哪些类可以继承一个给定的类或者实现一个给定的…...

鸿蒙如何自动生成二维码?QRCode组件

QRCode 用于显示单个二维码的组件。 说明&#xff1a; 该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 二维码组件的像素点数量与内容有关&#xff0c;当组件尺寸过小时&#xff0c;可能出现无法展示内容的情况&…...

【分布式知识】MapReduce详细介绍

文章目录 MapReduce概述1. MapReduce编程模型Map阶段Reduce阶段 2. Shuffle和Sort阶段3. MapReduce作业的执行流程4. MapReduce的优化和特性5. MapReduce的配置和调优 MapReduce局限性相关文献 MapReduce概述 MapReduce是一个分布式计算框架&#xff0c;它允许用户编写可以在大…...

JAVA八股

快速失败&#xff08;fail-fast&#xff09; 设计的目的是为了避免在遍历时对集合进行并发修改&#xff0c;从而引发潜在的不可预料的错误。 通过迭代器遍历集合时修改集合&#xff1a; 如果你使用Iterator遍历集合&#xff0c;然后直接使用集合的修改方法&#xff08;如add(…...

关于武汉芯景科技有限公司的限流开关芯片XJ6288开发指南(兼容SY6288)

一、芯片引脚介绍 1.芯片引脚 二、系统结构图 三、功能描述 1.EN引脚控制IN和OUT引脚的通断 2.OCB引脚指示状态 3.过流自动断开...

指令:计算机的语言(五)

2.9 人机交互 ASCII与二进制 对应表略 字节转移指令 lbu&#xff1a;加载无符号字节&#xff0c;从内存中加载1个字节&#xff0c;放在寄存器最右边8位。 sb&#xff1a;存储字节指令&#xff0c;从寄存器的最右边取1个字节并将其写入内存。 复制1个字节顺序如下&#xf…...

C#笔记(1)

解决方案&#xff1a; 【1】组织项目&#xff1a;把项目放在放在一个解决方案中&#xff0c;统一开发&#xff0c;统一编译。 【2】管理项目&#xff1a;开发中的任何问题&#xff0c;在统一编译过程中&#xff0c;都能随时发现。也可以添加第三方的库文件。 命名空间: 命名空…...

SSDF攻击、防御与展望

摘要&#xff1a; 随着无线通信业务的不断发展&#xff0c;频域也越来越成为了一种珍贵的稀缺资源&#xff0c;与此同时&#xff0c;相应的无线电安全问题层出不穷&#xff0c;为无线通信造成了十分恶劣的影响&#xff0c;本文从深入理解认知无线电安全开始&#xff0c;对一些典…...

MedMamba代码解释及用于糖尿病视网膜病变分类

MedMamba原理和用于糖尿病视网膜病变检测尝试 1.MedMamba原理 MedMamba发表于2024.9.28&#xff0c;是构建在Vision Mamba基础之上&#xff0c;融合了卷积神经网的架构&#xff0c;结构如下图&#xff1a; 原理简述就是图片输入后按通道输入后切分为两部分&#xff0c;一部分走…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...