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

LeetCode 25. K 个一组翻转链表

原题链接

难度:hard\color{red}{hard}hard

题目描述

给你链表的头节点 headheadheadkkk 个节点一组进行翻转,请你返回修改后的链表。

kkk 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 kkk 的整数倍,那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

示例 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]
复制示例输入

提示:

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

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


算法

(模拟)

  1. 增加虚拟头结点 dummy
  2. 对于每一轮的修改,求出 end 指针为下一轮需要交换的最后一个结点;在找 end 的过程中,若不足 k 个结点,则直接终止循环。
  3. 在找到 end 后,设置 ab 两个指针修改相邻结点之间的连接关系,需要一个临时的 c 指针来指向 bnext。(参考代码)
  4. 最终修改 p->nextc->next
  5. p 指向下一轮修改的起始位置的前一个位置。

在这里插入图片描述

C++ 代码

/*** 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) {}* };*/
class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode* dummy = new ListNode(0, head);for (auto p = dummy;;) {auto end = p;for (int i = 0; i < k && end != NULL; i ++) end = end->next;if (end == NULL) break;auto a = p->next, b = a->next;for (int i = 0; i < k - 1; i ++) {auto c = b->next;b->next = a;a = b, b = c;}auto c = p->next;p->next = a, c->next = b;p = c;}return dummy->next;}
};

相关文章:

LeetCode 25. K 个一组翻转链表

原题链接 难度&#xff1a;hard\color{red}{hard}hard 题目描述 给你链表的头节点 headheadhead &#xff0c; kkk 个节点一组进行翻转&#xff0c;请你返回修改后的链表。 kkk 是一个正整数&#xff0c;它的值小于或等于链表的长度。如果节点总数不是 kkk 的整数倍&#xf…...

朗润国际期货招商:历次科技风头下巨头的博弈

历次科技风头下巨头的博弈 VR/AR、区块链、折叠屏、元宇宙、AIGC五轮科技风头下巨头们都进场了吗&#xff1f; VR/AR硬件 谷歌&#xff1a;2014年入局&#xff0c;推出AR眼镜 百度&#xff1a;未入局 京东&#xff1a;未入局 腾讯&#xff1a;传要开发 亚马逊&#xff1…...

配置中心Config

引入依赖<parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.0.6.RELEASE</version></parent><properties><spring-cloud.version>Finchley.SR…...

【原创】java+jsp+servlet学生信息管理系统(jdbc+ajax+filter+cookie+分页)

一直想写一个比较基础的JavaWeb项目&#xff0c;然后综合各种技术&#xff0c;方便Java入门者进行学习。学生信息管理系统大家一般接触的比较多&#xff0c;那么就以这个为例来写一个基础项目吧。 需求分析&#xff1a; 使用jspservletmysql开发的学生信息管理系统&#xff0…...

链表题目总结 -- 回文链表

目录一. 从中心开始找最大的回文字符串1. 思路简述2. 代码3. 总结二. 判断是否为回文字符串1. 思路简述2. 代码3.总结三. 判断是否是回文链表1. 思路简述2. 代码3. 总结4. 优化解法一. 从中心开始找最大的回文字符串 题目链接&#xff1a;没有。给定一个字符串s&#xff0c;从…...

JAVA集合之List >> Arraylist/LinkedList/Vector结构

在Java开发过程中&#xff0c;可能经常会使用到List作为集合来使用&#xff0c;List是一个接口承于Collection的接口&#xff0c;表示着有序的列表。而我们要讨论的是它下面的实现类Arraylist/LinkedList/Vector的数据结构及区别。 ArrayList ArrayList&#xff1a;底层为数组…...

Linux多进程开发

一、进程概述 1、程序和进程 程序是包含一系列信息的文件&#xff0c;这些信息描述了如何在运行时创建一个进程&#xff1a; 二进制格式标识&#xff1a;每个程序文件都包含用于描述可执行文件格式的元信息。内核利用此信息来解释文件中的其他信息。&#xff08;ELF可执行连…...

三维重建小有基础入门之特征点检测基础

前言&#xff1a;本文将从此篇开始&#xff0c;记录自己从普通CVer入门三维重建的学习过程&#xff0c;可能过程比较坎坷&#xff0c;都在摸索阶段&#xff0c;但争取每次学习都能进一步&#xff0c;提高自己的能力&#xff0c;同时&#xff0c;每篇文章都会按情况相应地推出B站…...

基于node.js+vue+mysql考研辅导学习打卡交流网站系统vscode

语言 node.js 框架&#xff1a;Express 前端:Vue.js 数据库&#xff1a;mysql 数据库工具&#xff1a;Navicat 开发软件&#xff1a;VScode 主要功能包括管理员&#xff1a;首页、个人中心、用户管理、每日打卡管理、考研学校管理、考研专业管理、直通车管理、学习教材管理、…...

【C++、数据结构】封装unordered_map和unordered_set(用哈希桶实现)

文章目录&#x1f4d6; 前言1. 复用同一个哈希桶⚡1.1 &#x1f300;修改后结点的定义1.2 &#x1f300;两个容器各自模板参数类型&#xff1a;2. 改造之后的哈希桶⛳3. 哈希桶的迭代器&#x1f525;3.1 &#x1f4a5;哈希桶的begin&#xff08;&#xff09;和 end&#xff08;…...

StratoVirt 的 vCPU 拓扑(SMP)

CPU 拓扑用来表示 CPU 在硬件层面的组合方式&#xff0c;本文主要讲解 CPU 拓扑中的 SMP&#xff08;Symmetric Multi-Processor&#xff0c;对称多处理器系统&#xff09;架构&#xff0c;CPU 拓扑还包括其他信息&#xff0c;比如&#xff1a;cache 等&#xff0c;这些部分会在…...

现在直播大部分都是RTMP RTMP VS RTC

一 RTMP 抓了下抖音直播的包&#xff0c;windows端&#xff0c;走的TCP&#xff0c;加密了&#xff0c;估计还是RTMP。 我以为直播带货&#xff0c;都是RTC了。 快手直播也是TCP&#xff0c;地址用了IPV6。 淘宝直播也是。现在大部分直播都是RTMP。 只有视频会议走的RTC。…...

【Unity实战100例】Unity循环UI界面切换卡片功能

目录 ​编辑 一:制作UI界面 二:代码逻辑 1.定义基础变量...

Monorepo or 物料市场?结合工作实际情况对公司现有前端体系的思考

前言 去年年中基于若依vue前端框架进行了改造&#xff0c;加上后端的配合&#xff0c;我写了一套脚手架和项目中后台模板。中后台模板中包含了许多基础代码&#xff0c;比如登录/注册、路由、权限等等相关功能。这个中后台模板是基于我们实际开发定制的&#xff0c;所以跟通用…...

GEE学习笔记八十八:在自己的APP中使用绘制矢量(上)

在GEE中尤其是自己的APP中调用绘制的矢量图形方法之前没有合适的方法&#xff0c;但是现在可以通过ui.Map.DrawingTools(...)以及ui.Map.GeometryLayer(...)结合来做。具体的API如下图&#xff1a; 在这一篇中我先通过一个简单的例子来展示一下使用这些API后可以实现什么效果&a…...

“笨办法”学Python 3 ——练习 39. 字典,可爱的字典

练习39 源代码 # create a mapping of state to abbreviation #创建一个州与缩写的映射 states {Oregon:OR,Florida:FL,California: CA, New York: NY,Michigan:MI} #创建一个字典&#xff0c;key为州名&#xff0c;value为州缩写#Create a basic set of states and some cit…...

模糊的照片如何修复清晰?

相信有很多人用手机拍照时&#xff0c;觉得拍出来的照片一定是很漂亮的&#xff0c;结果拍了之后&#xff0c;拿出来一看模糊一片&#xff0c;根本看不清是什么。或者是只显示一半另一半模糊一片。而这些精彩瞬间很多时候是无法重拍的。虽然谁也不想拍出的照片出现模糊&#xf…...

如何理解​session、cookie、token的区别与联系?

session、cookie、token。 相信学过接口的朋友都特别熟悉了。 但是对我一个刚接触接口测试的小白来说&#xff0c;属实有点分不清楚。 下文就是我通过查阅各种资料总结出来的一点理解&#xff0c;不准确的地方还请各位指正。 &#xff08;文末送洗浴中心流程指南&#xff09…...

【MyBatis】| MyBatis分页插件PageHelper

目录 一&#xff1a;MyBatis使⽤PageHelper 1. limit分⻚ 2. PageHelper插件 一&#xff1a;MyBatis使⽤PageHelper 1. limit分⻚ &#xff08;1&#xff09;概念&#xff1a; ①页码&#xff1a;pageNum&#xff08;用户会发送请求&#xff0c;携带页码pageNum给服务器&am…...

Java枚举类详解

一、定义格式 public enum s { 枚举项1,枚举项2,枚举项3; } // 定义一个枚举类&#xff0c;用来表示春&#xff0c;夏&#xff0c;秋&#xff0c;冬这四个固定值 public enum Season {SPRING,SUMMER,AUTUMN,WINTER; } 二、枚举的特点 1、所有枚举类都是Enum的子类 2、我们可以通…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...