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

LeetCode 热题 100_K 个一组翻转链表(31_25_困难_C++)(四指针法)

LeetCode 热题 100_K 个一组翻转链表(31_25)

    • 题目描述:
    • 输入输出样例:
    • 题解:
      • 解题思路:
        • 思路一(四指针法):
      • 代码实现
        • 代码实现(思路一(四指针法)):

题目描述:

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

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

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

输入输出样例:

示例 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]

提示:
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

题解:

解题思路:

思路一(四指针法):

1、通过题目分析,在每次翻转前需要进行个数的判断,若满足再将k个结点翻转,将翻转后的答案进行连接。
我们发现我们在进行翻转的时候需要保存k个结点的首和尾(kHead和kTail),并且还需要保存kHead之前的一个结点(ansTail)和kTail之后的一个结点(next_kHead),方便将翻转后的链表进行连接和剩余结点的处理,因此我们需要四个指针(kHead、kTail、ansTail、next_kHead)。

具体实现思路请看下图:
请添加图片描述

代码实现

代码实现(思路一(四指针法)):
//判断剩余长度是否>=k,不够则返回nullptr,够则返回k个长度链表的尾结点 
ListNode *judgeLen_k(ListNode *kHead,int k){while(k-1){if(kHead==nullptr){return nullptr;}kHead=kHead->next;--k;}return kHead; 
} //翻转固定个数的链表,返回翻转后的头结点 
ListNode *reverseList_k(ListNode *kHead,int k){ListNode *pre=nullptr,*r=kHead,*tmp=kHead;while(k){r=r->next;tmp->next=pre;pre=tmp;tmp=r;--k;}return pre;
} //K 个一组翻转链表
ListNode* reverseKGroup(ListNode* head, int k) {ListNode *dummyHead=new ListNode(0); //存储答案的尾结点 ListNode *ansTail=dummyHead;//交换前,k个结点的头ListNode *kHead=head;//交换前,k个结点的末尾,不够k个则为nullptr ListNode *kTail=judgeLen_k(kHead,k);//保存下一个区间的头ListNode *next_kHead=nullptr;while(kTail!=nullptr){//保存下一个区间的头next_kHead=kTail->next;//翻转k个结点reverseList_k(kHead,k);//将k个结点翻转后的链表,连接到答案列表 ansTail->next=kTail;kHead->next=next_kHead;//更新答案链表的尾结点ansTail=kHead;//更新交换前,k个结点的头 kHead=next_kHead; //判断之后的结点是否够k个 kTail=judgeLen_k(next_kHead,k);} ListNode *ansHead=dummyHead->next;delete dummyHead;return ansHead;         
} 

代码调试

#include<iostream>
#include<vector>
using namespace std;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){}
}; //尾插法创建单链表
ListNode *createList(vector<int> arr){ListNode *head=nullptr,*tail=nullptr;for(const auto &val:arr){if(head==nullptr){head=tail=new ListNode(val);}else{tail->next=new ListNode(val);tail=tail->next;}}return head;
} //判断剩余长度是否>=k,不够则返回nullptr,够则返回k个长度链表的尾结点 
ListNode *judgeLen_k(ListNode *kHead,int k){while(k-1){if(kHead==nullptr){return nullptr;}kHead=kHead->next;--k;}return kHead; 
} //翻转固定个数的链表,返回翻转后的头结点 
ListNode *reverseList_k(ListNode *kHead,int k){ListNode *pre=nullptr,*r=kHead,*tmp=kHead;while(k){r=r->next;tmp->next=pre;pre=tmp;tmp=r;--k;}return pre;
} //K 个一组翻转链表
ListNode* reverseKGroup(ListNode* head, int k) {ListNode *dummyHead=new ListNode(0); //存储答案的尾结点 ListNode *ansTail=dummyHead;//交换前,k个结点的头ListNode *kHead=head;//交换前,k个结点的末尾,不够k个则为nullptr ListNode *kTail=judgeLen_k(kHead,k);//保存下一个区间的头ListNode *next_kHead=nullptr;while(kTail!=nullptr){//保存下一个区间的头next_kHead=kTail->next;//翻转k个结点reverseList_k(kHead,k);//将k个结点翻转后的链表,连接到答案列表 ansTail->next=kTail;kHead->next=next_kHead;//更新答案链表的尾结点ansTail=kHead;//更新交换前,k个结点的头 kHead=next_kHead; //判断之后的结点是否够k个 kTail=judgeLen_k(next_kHead,k);} ListNode *ansHead=dummyHead->next;delete dummyHead;return ansHead;         
} int main(){vector<int> a={1,2,3,4,5};int k=2;ListNode *head=createList(a);ListNode *test=reverseKGroup(head,k); while(test!=nullptr){cout<<test->val<<"->";test=test->next;}cout<<"null"; return 0;
}

反转链表(23_206_简单_C++)(单链表_迭代_递归):有关反转链表的知识请点击此链接

LeetCode 热题 100_K 个一组翻转链表(31_25)原题链接
欢迎大家和我沟通交流(✿◠‿◠)

相关文章:

LeetCode 热题 100_K 个一组翻转链表(31_25_困难_C++)(四指针法)

LeetCode 热题 100_K 个一组翻转链表&#xff08;31_25&#xff09; 题目描述&#xff1a;输入输出样例&#xff1a;题解&#xff1a;解题思路&#xff1a;思路一&#xff08;四指针法&#xff09;&#xff1a; 代码实现代码实现&#xff08;思路一&#xff08;四指针法&#x…...

Pytorch | 从零构建MobileNet对CIFAR10进行分类

Pytorch | 从零构建MobileNet对CIFAR10进行分类 CIFAR10数据集MobileNet设计理念网络结构技术优势应用领域 MobileNet结构代码详解结构代码代码详解DepthwiseSeparableConv 类初始化方法前向传播 forward 方法 MobileNet 类初始化方法前向传播 forward 方法 训练和测试训练代码…...

CSS系列(18)-- 工程化实践详解

前端技术探索系列&#xff1a;CSS 工程化实践详解 &#x1f3d7;️ 致读者&#xff1a;探索 CSS 工程化之路 &#x1f44b; 前端开发者们&#xff0c; 今天我们将深入探讨 CSS 工程化实践&#xff0c;学习如何在大型项目中管理 CSS。 工程化配置 &#x1f680; 项目结构 …...

日拱一卒(18)——leetcode学习记录:二叉树中的伪回文路径

一、题目 给你一棵二叉树&#xff0c;每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的&#xff0c;当它满足&#xff1a;路径经过的所有节点值的排列中&#xff0c;存在一个回文序列。 请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。 二、思路 …...

hive—炸裂函数explode/posexplode

1、Explode炸裂函数 将hive某列一行中复杂的 array 或 map 结构拆分成多行&#xff08;只能输入array或map&#xff09; 语法&#xff1a; select explode(字段) as 字段命名 from 表名; 举例&#xff1a; 1&#xff09;explode(array)使得结果中将array列表里的每个元素生…...

SpringBoot 新特性

优质博文&#xff1a;IT-BLOG-CN 2.1.0新特性最低支持jdk8,支持tomcat9 对响应式编程的支持&#xff0c;spring-boot-starter-webflux starter POM可以快速开始使用Spring WebFlux&#xff0c;它由嵌入式Netty服务器支持 1.5.8 2.1.0/2.7.0/3.0.0 Configuration propertie…...

鸿蒙app封装 axios post请求失败问题

这个问题是我的一个疏忽大意&#xff0c;在这里记录一下。如果有相同问题的朋友&#xff0c;可以借鉴。 当我 ohpm install ohos/axios 后&#xff0c;进行简单post请求验证&#xff0c;可以请求成功。 然后&#xff0c;我对axios 进行了封装。对axios 添加请求拦截器/添加响…...

消息队列 Kafka 架构组件及其特性

Kafka 人们通常有时会将 Kafka 中的 Topic 比作队列&#xff1b; 在 Kafka 中&#xff0c;数据是以主题&#xff08;Topic&#xff09;的形式组织的&#xff0c;每个 Topic 可以被分为多个分区&#xff08;Partition&#xff09;。每个 Partition 是一个有序的、不可变的消息…...

网络攻击与防范

目录 选填 第一章 1、三种网络模式 2、几种创建网络拓扑结构 NAT模式 VPN模式 软路由模式1 软路由模式2 3、Linux网络配置常用指令 4、常见网络服务配置 DHCP DNS Web服务与FTP服务 FTP用户隔离 第二章 DNS信息收集&#xff08;dnsenum、dnsmap&#xff09; 路…...

文献研读|基于像素语义层面图像重建的AI生成图像检测

前言&#xff1a;本篇文章主要对基于重建的AI生成图像检测的四篇相关工作进行介绍&#xff0c;分别为基于像素层面重建的检测方法 DIRE 和 Aeroblade&#xff0c;以及基于语义层面重建的检测方法 SimGIR 和 Zerofake&#xff1b;并对相应方法进行比较。 相关文章&#xff1a;论…...

【操作系统】为什么需要架构裁剪?

为什么需要架构裁剪&#xff1f; 原因 减小核心大小提高架构初始化速度降低内存占用提高系统性能移除不需要的功能&#xff0c;增加安全性 裁剪方法 初始化配置设置功能模块化移除不需要的驱动底层 一般裁剪对象&#xff08;以操作系统为例&#xff09; 文件系统的支持网…...

LSTM长短期记忆网络

LSTM&#xff08;长短期记忆网络&#xff09;数学原理 LSTM&#xff08;Long Short-Term Memory&#xff09;是一种特殊的递归神经网络&#xff08;RNN&#xff09;&#xff0c;解决了标准RNN中存在的梯度消失&#xff08;Vanishing Gradient&#xff09; 和**梯度爆炸&#x…...

基于前端技术UniApp和后端技术Node.js的电影购票系统

文章目录 摘要Abstruct第一章 绪论1.1 研究背景与意义1.2 国内外研究现状 第二章 需求分析2.1 功能需求分析2.2 非功能性需求分析 第二章系统设计3.1 系统架构设计3.1.1 总体架构3.1.2 技术选型 3.2 功能架构 第四章 系统实现4.1 用户端系统实现4.1.1 用户认证模块实现4.1.2 电…...

数据结构与算法:稀疏数组

前言 此文以整型元素的二维数组为例&#xff0c;阐述稀疏数组的思想。其他类型或许有更适合压缩算法或者其他结构的稀疏数组&#xff0c;此文暂不扩展。 稀疏数组的定义 在一个二维数据数组里&#xff0c;由于大量的元素的值为同一个值&#xff0c;比如 0或者其他已知的默认值…...

Meta重磅发布Llama 3.3 70B:开源AI模型的新里程碑

在人工智能领域&#xff0c;Meta的最新动作再次引起了全球的关注。今天&#xff0c;我们见证了Meta发布的Llama 3.3 70B模型&#xff0c;这是一个开源的人工智能模型&#xff0c;它不仅令人印象深刻&#xff0c;而且在性能上达到了一个新的高度。 一&#xff0c;技术突破&#…...

VSCode中的Black Formatter没有生效的解决办法

说明 如果正常按照配置进行的话&#xff0c;理论上是可以生效的。 "[python]": {"editor.defaultFormatter": "ms-python.black-formatter","editor.formatOnSave": true }但我在一种情况下发现不能生效&#xff0c;应为其本身的bug…...

【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题

目录 背包问题简介 问题描述 输入&#xff1a; 输出&#xff1a; 动态规划解法 动态规划状态转移 代码实现 代码解释 动态规划的时间复杂度 例子解析 输出&#xff1a; 总结 作者我蓝桥杯&#xff1a;2023第十四届蓝桥杯国赛C/C大学B组一等奖&#xff0c;所以请听我…...

Odoo:免费开源ERP的AI技术赋能出海企业电子商务应用介绍

概述 伴随电子商务的持续演进&#xff0c;客户对于便利性、速度以及个性化服务的期许急剧攀升。企业务必要探寻创新之途径&#xff0c;以强化自身运营&#xff0c;并优化购物体验。达成此目标的最为行之有效的方式之一&#xff0c;便是将 AI 呼叫助手融入您的电子商务平台。我们…...

微信小程序苹果手机自带的数字键盘老是弹出收起,影响用户体验,100%解决

文章目录 1、index.wxml2、index.js3、index.wxss1、index.wxml <!--index.wxml--> <view class="container"><view class="code-input-container"><view class="code-input-boxes"><!-- <block wx:for="{{…...

sql中case when若条件重复 执行的顺序

sql case when若条件重复 执行的顺序 在 SQL 中&#xff0c;如果你在 CASE 表达式中定义了多个 WHEN 子句&#xff0c;并且这些条件有重叠&#xff0c;那么 CASE 表达式的执行顺序遵循以下规则&#xff1a; &#xff08;1&#xff09;从上到下&#xff1a;SQL 引擎会按照 CASE …...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...

AD学习(3)

1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分&#xff1a; &#xff08;1&#xff09;PCB焊盘&#xff1a;表层的铜 &#xff0c;top层的铜 &#xff08;2&#xff09;管脚序号&#xff1a;用来关联原理图中的管脚的序号&#xff0c;原理图的序号需要和PCB封装一一…...