首页/新闻资讯/正文详情

【链表】LC 25.K 个一组翻转链表

发布时间:2026/11/3 10:37:07 来源:云帆数科 栏目:资讯中心
【链表】LC 25.K 个一组翻转链表
文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接25.K 个一组翻转链表2、题目描述二、个人思路整理1、思路分析核心思路先统计总长用剩余长度控制循环每组内部用双指针原地翻转再完成组间拼接统计总长先遍历一遍链表求出总节点数n。之后每翻转一组就执行n - k只要n k就继续这样无需每次翻转前“先探路走k kk步”判断剩余节点是否够一组逻辑更简洁。初始化哨兵节点与组前驱指针dummy哨兵节点指向原始head避免第一组翻转后头节点发生变化、需要特殊处理让“头节点所在组被翻转”与“中间组被翻转”走同一套代码。p0当前组的前驱节点指向当前待翻转分组的前一个节点初始指向dummy每翻转完一组就移动到当前组的新尾巴。组内反转每进入新一组都在循环内部重新声明pre nullptr、cur p0-next保证每组从干净状态开始翻转。pre已经翻转的部分指向反转链表的前一个节点最终指向当前组的新头。cur当前正在处理的节点指向当前需要翻转的节点最终停在下一组的头节点。用for (int i 0; i k; i)循环k kk次执行最基础的链表反转tmp cur-next; cur-next pre; pre cur; cur tmp;。k kk次循环结束后pre停在当前组的新头节点cur停在下一组的头节点而p0-next依然指着当前组原本的头节点现在变成了当前组的尾节点。组间拼接与指针推进先用next_p0 p0-next暂存当前组的新尾因为下一步会覆盖p0-next。让当前组的新尾连上下一组的头p0-next-next cur;让上一组的尾巴连上当前组的新头p0-next pre;将p0推进到当前组的新尾即next_p0准备处理下一组。循环结束后返回dummy.next由于头节点所在组可能已被翻转最终头节点不一定是原head必须返回哨兵的后继。2、解题代码/** * 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) {} * }; */classSolution{public:ListNode*reverseKGroup(ListNode*head,intk){intn0;ListNode*curhead;while(cur!nullptr){n;curcur-next;}ListNodedummy(0,head);ListNode*p0dummy;// p0指向当前组的前驱节点while(nk){n-k;// 每组重新开始翻转ListNode*prenullptr;ListNode*curp0-next;for(inti0;ik;i){ListNode*tmpcur-next;cur-nextpre;precur;curtmp;}// 组间拼接ListNode*next_p0p0-next;p0-next-nextcur;p0-nextpre;p0next_p0;}returndummy.next;}};复杂度分析时间复杂度O ( N ) O(N)O(N)遍历两次一次算长度一次做翻转。空间复杂度O ( 1 ) O(1)O(1)仅在栈上分配了一个dummy对象和几个指针。三、知识风暴链表分组翻转Reverse Nodes in k-Group是本题的核心题目要求把链表每k kk个节点视为一组组内原地翻转不足k kk个的尾部保持原样。它本质上是「基础链表反转」的升级版——把一次整体反转拆成若干次定长反转并在组与组之间做好衔接。算法核心思想先统计总长用长度控制循环先遍历一遍求出节点总数n之后每翻转一组就执行n - k只要n k就继续。这样无需每次翻转前“探路走k kk步”判断剩余节点是否够一组逻辑更简洁。哨兵节点统一边界引入dummy指向head让“头节点所在组被翻转”与“中间组被翻转”走同一套代码避免单独处理头节点。组内头插式反转在每组内部用pre/cur双指针循环k kk次完成反转k kk次结束后pre是新头、cur是下一组的头而p0-next仍指向本组旧头即反转后的新尾。两步完成衔接p0-next-next cur让本组新尾接上下一组p0-next pre让上一组尾巴接上本组新头最后把p0推进到本组新尾准备处理下一组。常见对比迭代原地翻转 vs 递归分组翻转迭代本题解法用dummyp0pre/cur在链表上原地操作空间复杂度O ( 1 ) O(1)O(1)是面试中最推荐的写法但指针较多衔接顺序写错容易断链需要理清“新头 / 新尾 / 下一组头”三者的关系。递归分组翻转先判断剩余节点是否够k kk个够则翻转前k kk个再递归处理后续部分并把本组新尾指向递归结果。代码更短、更贴近分治直觉但递归深度为O ( n / k ) O(n/k)O(n/k)存在栈开销。借助数组 / 栈把每组节点值压入栈再弹出重写思路直观、不易出错但需要额外O ( k ) O(k)O(k)空间且只改值不改节点不符合“原地翻转节点”的题意要求。指针衔接的关键细节为什么先存next_p0执行p0-next pre之后原来的p0-next本组新尾就被覆盖了所以必须先用next_p0暂存再把它作为下一轮的p0。pre的复位每进入新一组前pre需要重新置为nullptr否则会把上一组的节点错误地接到本组新头之后。不足k kk个的处理由于循环条件是n k剩余不足k kk个的节点根本不会进入翻转逻辑天然保持原顺序无需额外判断。使用要点长度先行先算n再翻转是本题最省心的写法务必牢记这个“用总长度控制循环”的套路。哨兵节点必备凡是涉及“可能翻转头节点”的链表题dummy都是降低边界复杂度的利器。画图验证指针组内反转 组间衔接共涉及 4 个指针建议在纸上画出dummy - 组1 - 组2的示意图逐步核对每一步的指向。返回dummy.next最终头节点可能已不是原head必须返回dummy.next而非head。算法变体与扩展两两交换链表中的节点LeetCode 24即k 2 k 2k2的特例可用同样的分组翻转框架也可用递归实现适合作为本题的热身。反转链表LeetCode 206本题组内反转的基础模板理解pre/cur双指针反转是解决本题的前提。反转链表 IILeetCode 92只翻转指定区间[ l e f t , r i g h t ] [left, right][left,right]与本题“定长分组翻转”互为补充可对比“区间边界定位”与“分组边界定位”的差异。K 个一组翻转链表递归写法同一道题的递归版本可与本题迭代写法对照体会“迭代控指针、递归控结构”的取舍。相关 LeetCode 例题206. 反转链表组内反转的基础模板92. 反转链表 II指定区间翻转对比24. 两两交换链表中的节点k 2 k2k2的特例143. 重排链表链表拆分与合并的综合应用

相关推荐

Bivane:React 组件库,PC 和 H5 交互分开适配
Bivane:React 组件库,PC 和 H5 交互分开适配

一套 API,两端各得其所。 One API. Screen-aware. Bivane 是一个 React 组件库:基于 React Tailwind CSS 实现,以 Vant 的设计语言为视觉源,以 shadcn copy-paste 形态分发进你的项目。 它的核心做法只有一句话——PC 和 H5 的… · 2026/11/3 10:37:07

本源之大美| 赵杰 | 量子哲学
本源之大美| 赵杰 | 量子哲学

作者:赵杰清华大学硕士、微美全息云科技(NASDAQ:WIMI)董事长、微算法科技(NASDAQ:MLGO)董事长、育杰奖学金创始人1. 《量子意识爱子论》本体根基宇宙最基础单元为爱子,同步承载意识、… · 2026/11/3 10:37:07

把决策模型从 API 里抢回来:33 毫秒定乾坤,这个 421M 的开源小模型正在重写 AI 成本账
把决策模型从 API 里抢回来:33 毫秒定乾坤,这个 421M 的开源小模型正在重写 AI 成本账

把决策模型从 API 里抢回来:33 毫秒定乾坤,这个 421M 的开源小模型正在重写 AI 成本账 先说一个很多公司每天都在上演的荒诞场景。 一封客户邮件进来,标题写着“三月被重复扣款,今天不退钱就退订”。系统其实只想知道三件事&#… · 2026/11/3 10:37:07

遗留系统接手难?用Zread从祖传代码生成可维护文档
遗留系统接手难?用Zread从祖传代码生成可维护文档

“祖传代码”这四个字,是从业者对遗留系统最客气的称呼。上周深夜有人发消息给我,说他接手了一个五年前的项目,仓库拉下来,README 六百字,三百字在讲怎么装环境,另外三百字介绍的是一个早就被删掉的模块。他… · 2026/11/4 4:37:45

L-Tester自动化测试平台:轻量级开源解决方案
L-Tester自动化测试平台:轻量级开源解决方案

1. 项目概述:L-Tester自动化测试平台L-Tester是一个面向现代软件开发的自动化测试开源项目,旨在为开发团队提供轻量级、可扩展的测试解决方案。不同于传统测试工具,它采用模块化架构设计,支持从单元测试到接口测试的全流程覆盖。我… · 2026/11/4 4:37:45

把Cursor接入蓝湖MCP:让AI直接读取设计稿参数,告别反复比对
把Cursor接入蓝湖MCP:让AI直接读取设计稿参数,告别反复比对

设计稿还原这件事,本质上是一场开发与设计之间的“信息损耗战”。设计师在蓝湖上把标注、切图、间距、颜色全部摆得清清楚楚,开发这边却还在对着设计稿放大镜式地量像素,写完代码后再被问一句“还原了吗”,然后开启新一轮的截图、… · 2026/11/4 4:37:45

3D网页游戏开发实测:Step 5 Preview、DeepSeek V4 Pro与GLM5.3代码生成能力对比
3D网页游戏开发实测:Step 5 Preview、DeepSeek V4 Pro与GLM5.3代码生成能力对比

这几天我把Step 5 Preview、DeepSeek V4 Pro、GLM5.3拉到同一个"考场"里,让它们各自从头写一个 3D 网页游戏。花了一天半,跑完三遍完整流程,中间经历了不少幺蛾子:浏览器白屏、角色原地起飞、模型对话跑偏、碰撞检测像开… · 2026/11/4 4:37:44

前端模块化与UMD:跨环境兼容解决方案
前端模块化与UMD:跨环境兼容解决方案

1. 前端模块化的江湖纷争:为什么需要UMD?作为一名经历过前端模块化"战国时代"的老兵,我至今还记得第一次被不同模块系统折磨得怀疑人生的场景。当时我写了个简单的日期格式化工具,在Vue项目里用ES6的import跑得好好的&a… · 2026/11/4 4:37:44

80X86微机接口实验硬核指南:FPGA引脚、时序控制与硬件调试实战
80X86微机接口实验硬核指南:FPGA引脚、时序控制与硬件调试实战

简介:本资源是面向高校《微机原理与接口技术》课程的配套实验教程,专为电子信息、自动化、计算机等专业本科生设计,聚焦80X86微处理器与外部硬件交互的工程实践能力培养。教程由西安唐都科教仪器公司官方编写,涵盖FPGA单元基础配置… · 2026/11/4 4:36:44

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 3:16:49

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 6:04:24

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 5:52:46

AI辅助技术栈评估:提升研发决策效率60%
AI辅助技术栈评估:提升研发决策效率60%

1. 项目背景与核心价值技术决策一直是研发团队面临的重大挑战。随着技术生态的快速演进,技术栈的选择、维护和迭代变得愈发复杂。我们团队在过去两年里,先后经历了三次重大技术栈迁移,每次都需要投入大量人力进行技术评估和风险分析。直到去年… · 2026/11/4 0:00:17

从生成Token到直接决策:Jev如何重塑AI Agent工程实践
从生成Token到直接决策:Jev如何重塑AI Agent工程实践

1. 从"生成文字"到"拍板决策":Jev 到底在解决什么问题大多数人第一次接触大模型,脑子里建立的模型是"输入问题、输出文字"。你问它今天天气怎么样,它给你一段描述;你让它写个周报,它给你… · 2026/11/4 0:00:17

32G统一内存跑大模型:内存账、TPS实测与端云分流
32G统一内存跑大模型:内存账、TPS实测与端云分流

想在一台 32G 统一内存的小主机上把大模型跑成"日常可用",这件事我前后折腾了小半年。标题里说的这台 Mac mini M6,是我们这次讨论的目标平台,具体到手规格以实物为准;但下面这套推算方法和实测思路,对任何统… · 2026/11/4 0:00:17

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 3:16:49

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 6:04:24

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 5:52:46

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码