【算法专题--链表】K个一组翻转链表 -- 高频面试题(图文详解,小白一看就懂!!!)

本文主要是介绍【算法专题--链表】K个一组翻转链表 -- 高频面试题(图文详解,小白一看就懂!!!),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一、前言

二、题目描述 

三、解题方法

⭐双指针 -- 采用哨兵位头节点

🥝 什么是哨兵位头节点?  

🍍 案例图解  

四、总结与提炼 

五、共勉 


一、前言

      K个一组翻转链表 这道题,可以说是--链表专题--,最经典的一道题,也是在面试中频率最高的一道题目,通常在面试中,面试官可能会从多个方面考察这道题目,所以大家需要对这道题目非常熟悉哦!!
      本片博客就来详细的讲讲解一下
K个一组翻转链表 的实现方法,让我们的面试变的更加顺利!!!

二、题目描述 

题目连接:25. K 个一组翻转链表 - 力扣(LeetCode)

三、解题方法

⭐双指针 -- 采用哨兵位头节点

🥝 什么是哨兵位头节点?  

首先,先来了解一下什么是  哨兵位---头节点   

  • 它是一个附加的链表结点,该 结点 作为 第一个节点它的数据域不存储任何东西,只是为了操作的方便而引入的。
  • 也就是说,如果一个链表有哨兵节点的话,那么链表表的第一个元素应该是链表的第二个节点。

  哨兵位 --- 头节点的作用:  

  • 比如向链表中插入一个节点,对于没有哨兵位单链表当待插入的节点为链表的第一个节点,由于没有前驱,需要进行特殊处理,从而代码的复杂性增加。 
  • 如果有哨兵位头节点,则第一个节点的处理方式与其它节点相同,可以统一进行处理

 🍍 解题思路  

根据题目要求,我们需要将链表中每 k 个节点翻转。我们先统计链表中的节点数,然后每 k 个节点作为一组,在这一组中进行链表翻转,翻转后我们利用一个节点 p0 将已经翻转的节点和接下来将要翻转的节点沟通起来。

🍍 案例图解  

 链表:【1,2,3,4,5】 

  •  创建 哨兵位头节点 和 双指针,开始遍历整个链表,并统计链表的节点个数 count = 5

  •  在外循环1 中,我们可以根据  反转链表 中讲过的三指针法,先将第一组的链表翻转,接着 更新指针 p0 ,指向第二组链表的头节点,同理可以得到 外循环 2 的结果

 复杂度分析 :

时间复杂度:O ( n ),n 为链表的节点个数

空间复杂度:O ( 1 )


 代码:

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {// 反转链表(三指针) + 哨兵位// 创建一个哨兵位 初始化为 -1,连接到 head 上ListNode* pre_head = new ListNode(-1,head);ListNode* p0  = pre_head;  // 用于连接反转后的链表// 统计链表有多少个节点int count = 0;ListNode* cur = head;while(cur){cur = cur->next;count++;}// 开始进行分组反转  --     三指针法ListNode* pre = nullptr;cur = head;for(int n = count ; n>=k ; n = n-k){// 反转局部链表,反转 k 个节点for(int i = 0; i < k ; i++){ListNode* nextnode = cur->next;cur->next = pre;pre = cur;cur = nextnode;}// 将反转的节点 和 要反转的的节点沟通起来ListNode* next = p0->next;p0->next->next = cur;p0->next = pre;p0 = next;  }// 返回哨兵位的 下一个节点return pre_head->next;}
};

四、总结与提炼 

        最后我们来总结一下本文所介绍的内容,本文讲解来一道力扣中有关 K个一组翻转链表的题目,这道题目是校招笔试面试中有关链表章节非常高频的一道题目大家下去一定要自己再画画图,分析一下,把这段代码逻辑自己实现一遍,才能更好地掌握 

五、共勉 

        以下就是我对 K个一组翻转链表 的理解,如果有不懂和发现问题的小伙伴,请在评论区说出来哦,同时我还会继续更新对 链表专题 的理解,请持续关注我哦!!! 

这篇关于【算法专题--链表】K个一组翻转链表 -- 高频面试题(图文详解,小白一看就懂!!!)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1072084

相关文章

Python标准库之数据压缩和存档的应用详解

《Python标准库之数据压缩和存档的应用详解》在数据处理与存储领域,压缩和存档是提升效率的关键技术,Python标准库提供了一套完整的工具链,下面小编就来和大家简单介绍一下吧... 目录一、核心模块架构与设计哲学二、关键模块深度解析1.tarfile:专业级归档工具2.zipfile:跨平台归档首选3.

idea的终端(Terminal)cmd的命令换成linux的命令详解

《idea的终端(Terminal)cmd的命令换成linux的命令详解》本文介绍IDEA配置Git的步骤:安装Git、修改终端设置并重启IDEA,强调顺序,作为个人经验分享,希望提供参考并支持脚本之... 目录一编程、设置前二、前置条件三、android设置四、设置后总结一、php设置前二、前置条件

python中列表应用和扩展性实用详解

《python中列表应用和扩展性实用详解》文章介绍了Python列表的核心特性:有序数据集合,用[]定义,元素类型可不同,支持迭代、循环、切片,可执行增删改查、排序、推导式及嵌套操作,是常用的数据处理... 目录1、列表定义2、格式3、列表是可迭代对象4、列表的常见操作总结1、列表定义是处理一组有序项目的

python使用try函数详解

《python使用try函数详解》Pythontry语句用于异常处理,支持捕获特定/多种异常、else/final子句确保资源释放,结合with语句自动清理,可自定义异常及嵌套结构,灵活应对错误场景... 目录try 函数的基本语法捕获特定异常捕获多个异常使用 else 子句使用 finally 子句捕获所

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3

SQL Server 中的 WITH (NOLOCK) 示例详解

《SQLServer中的WITH(NOLOCK)示例详解》SQLServer中的WITH(NOLOCK)是一种表提示,等同于READUNCOMMITTED隔离级别,允许查询在不获取共享锁的情... 目录SQL Server 中的 WITH (NOLOCK) 详解一、WITH (NOLOCK) 的本质二、工作

springboot自定义注解RateLimiter限流注解技术文档详解

《springboot自定义注解RateLimiter限流注解技术文档详解》文章介绍了限流技术的概念、作用及实现方式,通过SpringAOP拦截方法、缓存存储计数器,结合注解、枚举、异常类等核心组件,... 目录什么是限流系统架构核心组件详解1. 限流注解 (@RateLimiter)2. 限流类型枚举 (

Java Thread中join方法使用举例详解

《JavaThread中join方法使用举例详解》JavaThread中join()方法主要是让调用改方法的thread完成run方法里面的东西后,在执行join()方法后面的代码,这篇文章主要介绍... 目录前言1.join()方法的定义和作用2.join()方法的三个重载版本3.join()方法的工作原

Spring AI使用tool Calling和MCP的示例详解

《SpringAI使用toolCalling和MCP的示例详解》SpringAI1.0.0.M6引入ToolCalling与MCP协议,提升AI与工具交互的扩展性与标准化,支持信息检索、行动执行等... 目录深入探索 Spring AI聊天接口示例Function CallingMCPSTDIOSSE结束语

C语言进阶(预处理命令详解)

《C语言进阶(预处理命令详解)》文章讲解了宏定义规范、头文件包含方式及条件编译应用,强调带参宏需加括号避免计算错误,头文件应声明函数原型以便主函数调用,条件编译通过宏定义控制代码编译,适用于测试与模块... 目录1.宏定义1.1不带参宏1.2带参宏2.头文件的包含2.1头文件中的内容2.2工程结构3.条件编