Java链表反转方法详解
一、理解链表结构
假设链表节点定义为:
class ListNode {int val;ListNode next;ListNode(int x) { val = x; } }
二、迭代法反转链表
核心思路
逐步反转每个节点的指针方向,最终使整个链表反向。
步骤拆解
-
初始化三个指针:
-
prev
:指向已反转部分的头节点(初始为null
)。 -
current
:指向待反转的当前节点(初始为头节点)。 -
next
:临时保存current.next
,防止断链。
-
-
循环操作:
-
保存
current
的下一个节点:next = current.next
。 -
反转指针:
current.next = prev
。 -
移动
prev
和current
:prev = current
,current = next
。
-
-
终止条件:当
current
为null
时,prev
就是新链表的头节点。
代码实现
public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode current = head;while (current != null) {ListNode next = current.next; // 保存下一个节点current.next = prev; // 反转指针prev = current; // prev 前移current = next; // current 前移}return prev; // 新头节点 }
示意图
初始状态:1 -> 2 -> 3 -> null 反转过程: Step 1: prev=null, current=1 → 1.next=null → prev=1, current=2 Step 2: prev=1, current=2 → 2.next=1 → prev=2, current=3 Step 3: prev=2, current=3 → 3.next=2 → prev=3, current=null 最终结果:3 -> 2 -> 1 -> null
三、递归法反转链表
核心思路
假设头节点后的子链表已反转,只需处理头节点与子链表的关系。
步骤拆解
-
终止条件:链表为空或只有一个节点,直接返回头节点。
-
递归反转子链表:
newHead = reverseList(head.next)
。 -
调整指针:
-
将头节点的下一个节点的
next
指向自己:head.next.next = head
。 -
断开原头节点的
next
指针:head.next = null
。
-
代码实现
public ListNode reverseList(ListNode head) {if (head == null || head.next == null) {return head; // 终止条件}ListNode newHead = reverseList(head.next); // 递归反转子链表head.next.next = head; // 反转指针head.next = null; // 断开原指针return newHead; // 始终返回新头节点 }
示意图
初始链表:1 -> 2 -> 3 -> null 递归过程: 递归到最深层:处理节点3 → 返回3 回归时处理节点2:2.next.next=2 → 3 -> 2,断开2.next → 3 -> 2 -> null 回归时处理节点1:1.next.next=1 → 2 -> 1,断开1.next → 3 -> 2 -> 1 -> null
四、分组反转链表
问题分析
目标:每 k 个节点为一组 反转链表,剩余不足 k 个的节点保持原顺序。
示例:
-
原链表:
1 → 2 → 3 → 4 → 5
,k=2
→ 反转后:2 → 1 → 4 → 3 → 5
-
原链表:
1 → 2 → 3 → 4 → 5
,k=3
→ 反转后:3 → 2 → 1 → 4 → 5
核心思路
-
分段处理:将链表按 k 个一组切割,逐组反转。
-
边界控制:
-
检查剩余节点是否足够 k 个。
-
反转后正确连接各组头尾节点。
-
-
递归或迭代:两种方法均可实现,迭代法更直观。
迭代法实现
步骤拆解
-
辅助节点:创建虚拟头节点
dummy
,简化头节点处理。 -
指针定义:
-
pre
:指向当前组的前一组的尾节点(初始为dummy
)。 -
start
:当前组的起始节点。 -
end
:当前组的结束节点。
-
-
循环处理:
-
定位每组起点
start
和终点end
。 -
若剩余节点不足 k 个,直接结束。
-
反转当前组,并调整
pre
、start
、end
的指针。
-
代码实现
public ListNode reverseKGroup(ListNode head, int k) {if (head == null || k == 1) return head;ListNode dummy = new ListNode(0);dummy.next = head;ListNode pre = dummy; // 前一组反转后的尾节点ListNode start = head; // 当前组的起始节点while (start != null) {ListNode end = pre; // 定位当前组的 end 节点for (int i = 0; i < k; i++) {end = end.next;if (end == null) return dummy.next; // 不足 k 个,直接返回}// 保存下一组的起始节点,并断开当前组ListNode nextGroup = end.next;end.next = null;// 反转当前组,并连接前一组的尾节点pre.next = reverse(start); // pre → 新头节点start.next = nextGroup; // 新尾节点 → 下一组// 移动 pre 和 start 到下一组pre = start;start = nextGroup;}return dummy.next; }// 反转单链表(基础迭代法) private ListNode reverse(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev; }
递归法实现
核心思路
-
递归反转每组:先反转前 k 个节点,再递归处理剩余链表。
-
边界检查:剩余节点不足 k 个时直接返回原链表。
代码实现
public ListNode reverseKGroup(ListNode head, int k) {if (head == null || k == 1) return head;// 检查剩余节点是否足够 k 个ListNode curr = head;int count = 0;while (curr != null && count < k) {curr = curr.next;count++;}if (count < k) return head; // 不足 k 个,不反转// 反转前 k 个节点ListNode newHead = reverse(head, k);// 递归处理剩余链表,并连接已反转的部分head.next = reverseKGroup(curr, k);return newHead; }// 反转前 k 个节点 private ListNode reverse(ListNode head, int k) {ListNode prev = null;ListNode curr = head;while (k-- > 0) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev; }
关键边界条件
-
链表长度不足 k:直接返回原链表。
-
k=1:无需反转。
-
头尾连接:反转后需要将前一组的尾节点连接到当前组的新头节点,当前组的尾节点连接到下一组的头节点。
代码对比
我自己对于迭代法进行优化,减少了一个linknode start。
public static ListNode reverseKGroup(ListNode head, int k) {if (head==null || k==1)return head;ListNode dummy = new ListNode(0);ListNode prev = dummy; // 用来记录每个分组的前节点,用于连结分组,赋值end移动等dummy.next = head; // 初始化虚拟头节点while (head!=null){ /// ListNode end=prev; // end节点 反转的最后一个节点for (int i = 0; i < k; i++) {end=end.next;if (end==null)return dummy.next; // 保持返回链表的最初头节点}ListNode next = end.next; // 用于保存下一组起始end.next=null;prev.next=reverse(head);// pre--> 新头节点 head用来反转的头节点,prev作为上一组来连结head.next=next; // 新尾点--> 下一组// 对pre重新赋值prev=head; // 上一组的尾节点head=next; //下一组的头节点 或者说往下移一步}return dummy.next;}public static ListNode reverse(ListNode head) {ListNode prev=null;ListNode curr=head;ListNode next=head.next;while(curr!=null){next=curr.next;curr.next=prev;prev=curr;curr=next;}return prev;}
力扣上官方代码
class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode hair = new ListNode(0);hair.next = head;ListNode pre = hair;while (head != null) {ListNode tail = pre;// 查看剩余部分长度是否大于等于 kfor (int i = 0; i < k; ++i) {tail = tail.next;if (tail == null) {return hair.next;}}ListNode nex = tail.next;ListNode[] reverse = myReverse(head, tail);head = reverse[0];tail = reverse[1];// 把子链表重新接回原链表pre.next = head;tail.next = nex;pre = tail;head = tail.next;}return hair.next;}public ListNode[] myReverse(ListNode head, ListNode tail) {ListNode prev = tail.next;ListNode p = head;while (prev != tail) {ListNode nex = p.next;p.next = prev;prev = p;p = nex;}return new ListNode[]{tail, head};}
}
相关文章:
Java链表反转方法详解
一、理解链表结构 假设链表节点定义为: class ListNode {int val;ListNode next;ListNode(int x) { val x; } } 二、迭代法反转链表 核心思路 逐步反转每个节点的指针方向,最终使整个链表反向。 步骤拆解 初始化三个指针: prev…...
lmm-r1开源程序是扩展 OpenRLHF 以支持 LMM RL 训练,用于在多模态任务上重现 DeepSeek-R1
一、软件介绍 文末提供程序和源码下载学习 lmm-r1开源程序是扩展 OpenRLHF 以支持 LMM RL 训练,用于在多模态任务上重现 DeepSeek-R1。 二、简介 小型 3B 大型多模态模型(LMMs)由于参数容量有限以及将视觉感知与逻辑推理相结合的固有复杂性…...
Java学习笔记(数组,方法)
一,数组 1.数组初始化 1.1动态初始化 格式:数据类型[] 数组名 new 数据类型[数组长度]; int[] arr new int[3]; // 定义长度为3的int数组,元素默认值为0 double[] scores new double[5]; // 长度5,元素默认0.0 String[…...
嵌入式---零点漂移(Zero Drift)
一、零点漂移的定义与本质 零点漂移(简称“零漂”)指传感器在输入信号为零(或理论上应输出固定零值)时,输出信号随时间、温度、环境等因素变化而偏离初始零点的现象。 核心特征:无输入时输出非零且缓慢变…...
健身房管理系统设计与实现(springboot+ssm+vue+mysql)含万字详细文档
健身房管理系统设计与实现(springbootssmvuemysql)含万字详细文档 健身房管理系统是一个全面的解决方案,旨在帮助健身房高效管理日常运营。系统主要功能模块包括个人中心、会员管理、员工管理、会员卡管理、会员卡类型管理、教练信息管理、解聘管理、健身项目管理、…...
C语言if
一、题目引入 如果从键盘输入58,则以下程序输出的结果是多少? 二、运行结果 三、题目分析 因为这道题中的多个if是并列结构 所以只要条件满足都会执行 这一题58满足所有的条件 所以可以运行出来 也就是说每个if里面的条件都满足 所以都会打印出来 而下面的这种情况就是 if e…...
XSS学习1之http回顾
1. HTTP的基本结构与工作流程 HTTP是一个请求-响应协议,基于客户端与服务器之间的交互。每次用户通过浏览器请求某个资源时,HTTP协议都会完成一系列的步骤。 HTTP请求: HTTP请求由以下几个部分构成: 请求行: 请求方…...
小迪抓包技术算法加密(6-9天)
抓包技术 https://blog.csdn.net/2301_81015455/article/details/147014382 算法加密入门(了解) 在实际测试中安全性高一些得采用得都是AES等高安全加密,遇到这种,放弃你啥都不知道测个毛啊,所以直接run!!! 大部分解密时碰撞式…...
Tkinter与ttk模块对比:构建现代 Python GUI 的进化之路
在 Python GUI 开发中,标准库 tkinter 及其子模块 ttk(Themed Tkinter)常被同时使用。本文通过功能对比和实际案例,简单介绍这两个模块的核心差异。 1. 区别 Tkinter:Python 标准 GUI 工具包(1994年集成&…...
【数据结构入门训练DAY-18】信息学奥赛一本通T1331-后缀表达式的值
文章目录 前言一、题目二、解题思路总结 前言 本次训练内容: 栈的复习。栈模拟四则运算计算问题的练习。训练解题思维。 一、题目 从键盘读入一个后缀表达式(字符串),只含有0-9组成的运算数及加()、减…...
时序预测 | Transformer-LSTM-SVM时间序列预测(Matlab完整源码和数据,适合基础小白研究)
时序预测 | Transformer-LSTM-SVM时间序列预测(Matlab完整源码和数据,适合基础小白研究) 目录 时序预测 | Transformer-LSTM-SVM时间序列预测(Matlab完整源码和数据,适合基础小白研究)效果一览基本介绍代码…...
【HarmonyOS 5】makeObserved接口详解
【HarmonyOS 5】makeObserved接口详解 一、makeObserved接口是什么? makeObserved 接口(API version 12 起可用)用于将非观察数据转为可观察数据,适用于三方包类、Sendable 装饰的类、JSON.parse 返回的对象、collections.Array…...
色谱图QCPColorMap
一、QCPColorMap 概述 QCPColorMap 是 QCustomPlot 中用于绘制二维颜色图的类,可以将矩阵数据可视化为颜色图(热力图),支持自定义色标和插值方式。 二、主要属性 属性类型描述dataQCPColorMapData存储颜色图数据的对象interpol…...
【数据结构_12】二叉树(4)
一、二叉树的层序遍历 思路:可以按照先序的方式来遍历这个树,递归的时候,给递归方法,加上辅助的参数,level表示当前层数,递归过程中,根据level的值,决定当前整个节点要放到哪个list中…...
HCIA-Datacom高阶:vlan、vlanif、单臂路由、静态路由、ospf综合实验
本实验拓扑图如下:实验包含 AR1、AR2、AR3 路由器,LSW1(三层交换机)、LSW2、LSW3 交换机,以及 PC1-4 和 Server1。AR1 与 LSW2 通过单臂路由连接,AR2 与 AR3、LSW1 构成 OSPF 网络,AR1 与 AR2 间…...
HTTP 1.0 和 2.0 的区别
HTTP 1.0 和 2.0 的核心区别体现在性能优化、协议设计和功能扩展上,以下是具体对比: 一、核心区别对比 特性HTTP 1.0HTTP 2.0连接方式非持久连接(默认每次请求新建 TCP 连接)持久连接(默认保持连接,可复用…...
如何一键批量删除多个 Word 文档中的页眉和页脚
在工作中,许多 Word 文档的页眉页脚中包含公司名称、Logo、电话等信息,用于对外宣传。但有时我们需要批量删除这些页眉页脚信息,尤其当信息有误时,手动逐个删除会增加工作量,导致效率低下。本文将介绍一种便捷的方法&a…...
关于编译树莓派内核系统的总结
1.首先获取官方的内核系统源码: 然后在源码根目录执行命令: 🌟ARCHarm64 CROSS_COMPILEaarch64-linux-gnu- KERNELkernel8 make bcm2712_defconfig (注意这里的是树莓派5的64位的) 🌟ARCHarm CROSS_COM…...
AIGC赋能插画创作:技术解析与代码实战详解
文章目录 一、技术架构深度解析二、代码实战:构建AIGC插画生成器1. 环境配置与依赖安装2. 模型加载与文本提示词构建3. 图像生成与参数调优4. 风格迁移与多模型融合 三、进阶技巧:参数调优与效果增强四、应用场景代码示例1. 游戏角色设计2. 广告海报生成…...
平衡二叉树(leetcode刷题)
题目描述: 给定一个二叉树,判断它是否是 平衡二叉树 (平衡二叉树 是指该树所有节点的左右子树的高度相差不超过 1。) 示例 1: 输入:root [3,9,20,null,null,15,7] 输出:true示例 2࿱…...
【数据结构 · 初阶】- 带环链表
目录 一.基本结构 二.判断一个单链表带不带环 三.2个问题 1.为什么 slow 走 1 步,fast 走 2 步,他们会相遇,会不会错过?请证明。 2.为什么 slow 走 1 步,fast 走 X 步 ( X > 3 ),他们会相遇&#x…...
ClickHouse简介
OLAP与ClickHouse的定位 OLAP的核心概念 OLTP:服务于高并发、低延迟的短事务操作(如银行转账、订单支付),强调数据的增删改查(CRUD)和事务一致性(ACID)。 OLAP:专注于大…...
强制重装及验证onnxruntime-gpu是否正确工作
#工作记录 我们经常会遇到明明安装了onnxruntime-gpu或onnxruntime后,无法正常使用的情况。 一、强制重新安装 onnxruntime-gpu 及其依赖 # 强制重新安装 onnxruntime-gpu 及其依赖 pip install --force-reinstall --no-cache-dir onnxruntime-gpu1.18.0 --extra…...
分布自定义shell脚本(详写)附带全代码
涉及知识全排列 常见指令 小知识点 操作系统 什么是进程 进程控制 步骤 1:项目准备 在开始编写代码之前,你需要创建一个新的项目文件夹,并在其中创建一个 .cpp 文件,例如 my_shell.cpp。同时,确保你已经安装了 C…...
windows拷贝文件脚本
1、新建脚本文件xxx.bat,名字任意,后缀未.bat即可,将以下内容拷贝进去,修改src和des为自己文件的目录即可。 echo off :: 设置字符集为UTF-8,命令窗口能正确显示中文字符。 chcp 65001 rem 读取当前目录并进入当前目…...
Arduino编译和烧录STM32——基于J-link SWD模式
一、安装Stm32 Arduino支持 在arduino中添加stm32的开发板地址:https://github.com/stm32duino/BoardManagerFiles/raw/main/package_stmicroelectronics_index.json 安装stm32开发板支持 二、安装STM32CubeProgrammer 从stm32网站中安装:https://ww…...
Java表达式2.0
1 .数据类型转换 自动类型转换的规则 自动类型转换遵循一定的规则,这些规则确保了转换的合理性和安全性。以下是自动类型转换的主要规则: 容量小的类型自动转换为容量大的类型 Java中,数据类型的容量从小到大依次为:byte → shor…...
【概率论,算法】排列的峰值期望
Surtr1 的珂学难题 题目链接:https://ac.nowcoder.com/acm/contest/107965/E 给定一个长度为 n n n 的排列 p p p,排列中任一位置如果满足以下条件,则称该位置为 峰值: 位置 1:若存在元素,满足 p [ 1 ] > p […...
清理C盘组合拳:最高释放空间80GB+
分享一套系统化的C盘清理方案,涵盖从基础清理到深度优化的8个关键步骤,结合安全性与效率,可快速释放5-50GB空间: 一、精准定位空间占用源(必备工具) 空间可视化分析 使用 TreeSize Free 或 WizTree 扫描C…...
容器中的对象切片问题
C 容器(如 std::vector、std::list 等) 通常存储对象的副本,而非指向对象的指针。因此,当与继承结合使用时,可能导致 切片(Object Slicing) 问题,即仅存储基类部分,丢失派…...
SpringBoot编写单元测试
pom.xml引入单元测试的坐标 <!--单元测试坐标--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-test</artifactId><scope>test</scope></dependency>编写单元测试类 测试类…...
二、在springboot 中使用 AIService
在上一篇文章中,我们介绍了如何使用langchain4j实现简单的问答功能,本篇文章我们将介绍如何在springboot中使用AIService。 1.实现原理 先看下AiService注解所在的依赖langchain4j-spring-boot-starter中包含什么内容: 1.1 event.AiServi…...
拼多多面经,暑期实习Java一面
项目中的设计模式 mysql连接过程,索引,分库分表场景,路由策略 redis使用场景,分片集群怎么搭建与路由,数据一致性 分布式锁怎么用的,具体使用参数 线程池怎么用的,过程 sql having 分布式事务 如…...
Function calling LLMs 的 MCP:AI开发的双剑合璧
🧠 向所有学习者致敬! “学习不是装满一桶水,而是点燃一把火。” —— 叶芝 我的博客主页: https://lizheng.blog.csdn.net 🌐 欢迎点击加入AI人工智能社区! 🚀 让我们一起努力,共创AI未来! 🚀 在 MCPs 成为主流(或者像现在这样火得一塌糊涂)之前,大多数 AI …...
数字系统与编码
1. 数字系统(Number Systems) 1.1 常见数字系统 系统基数符号集示例应用场景二进制20, 11010计算机底层电路、数据存储八进制80-717Unix文件权限(如chmod 755)十进制100-942日常计算十六进制160-9, A-F0x1F内存地址、颜色编码&a…...
Pytorch实战
1、安装 安装 conda, Python工具大全,方便管理多个 Python 环境,必须选择跟自己环境配套的版本。 https://www.anaconda.com 网速慢的,可以参考国内源,也可以去这里看看: torch PyPI Index of /anaconda/miniconda…...
如何高效利用呼叫中心系统和AI语音机器人
要更好地使用呼叫中心系统和语音机器人,需要结合两者的优势,实现自动化、智能化、高效率的客户服务与业务运营。以下是优化策略和具体实践方法: 一、呼叫中心系统优化 1. 智能路由与IVR优化 智能ACD(自动呼叫分配) …...
LeetCode[232]用栈实现队列
思路: 一道很简单的题,就是栈是先进后出,队列是先进先出,用两个栈底相互对着,这样一个队列就产生了,右栈为空的情况,左栈栈底就是队首元素,所以我们需要将左栈全部压入右栈ÿ…...
using用法整理
using 的极简新手教程,用最直白的语言和代码解释: 美图美图 一、核心作用:给类型起别名 目的:让复杂类型名变短、变好记。 例子: // 原名:std::vector<std::string> // 起个别名就叫 StringList…...
《猎豹夕阳》
年少时很喜欢的一篇文章,曾和挚友一遍又一遍的记诵,今天又偶然遇到他,转载如下: 我第一次见到它,是在风雪的夜里。我不会抱怨这种天气,因为我是个优秀的登山探险者,我必须在这种天气下工作。我…...
【AI训练环境搭建】在Windows11上搭建WSL2+Ubuntu22.04+Tensorflow+GPU机器学习训练环境
一、安装Ubuntu 拿到该文件Ubuntu-22.04.tar 通过wsl导入该虚拟机镜像,然后查看wsl虚拟机列表。 wsl --import Ubuntu-22.04-tensorflow D:\wsl-data\Ubuntu-22.04-tensorflow D:\wsl-data\temp\Ubuntu-22.04.tarwsl -l 进入虚拟机 wsl -d Ubuntu-22.04-tensorfl…...
如何轻松实现用户充值系统的API自动化测试
在现代软件开发中,API(应用程序编程接口)作为连接不同系统和模块的关键组件,其重要性日益凸显。随着软件应用的互联性不断增强,API的数量和复杂度也在不断增加。传统的API测试方法面临着诸多挑战: 1.手动测…...
Python 一等函数( 高阶函数)
高阶函数 接受函数为参数,或者把函数作为结果返回的函数是高阶函数(higherorder function)。map 函数就是一例,如示例 5-2 所示。此外,内置函 数 sorted 也是:可选的 key 参数用于提供一个函数,…...
用于手部康复设备的TinyML语音分类嵌入式人工智能模块
论文标题 英文标题:TinyML Speech Classification Embedded AI Module for Hand Rehabilitation Device 中文标题:用于手部康复设备的 TinyML 语音分类嵌入式人工智能模块 作者信息 Arkorn Numsomran:Triam Udom Suksa Pattanakarn Suvarna…...
【HarmonyOS 5】VisionKit人脸活体检测详解
【HarmonyOS 5】VisionKit人脸活体检测详解 一、VisionKit人脸活体检测是什么? VisionKit是HamronyOS提供的场景化视觉服务工具包。 华为将常见的解决方案,通常需要三方应用使用SDK进行集成。华为以Kit的形式集成在HarmoyOS系统中,方便三方…...
Linux操作系统--进程的创建和终止
目录 1.进程创建 1.1fork()函数初识 1.2写时拷贝 1. 提升系统效率 2. 隔离错误影响 3. 支持并行计算 2.进程终止: 2.1进程退出场景: 2.2进程常见退出方法: 2.3_exit()系统调用接口 2.4exit函数 2.5return退出 1.进程创建 1.1for…...
算法分析传输加密数据格式密文存储代码混淆逆向保护
代码混淆 一.基本概念java的bytecode很容易通过JAD等反编译工具还原出源代码。这样势必不满足安全的定义。如何一定程度上保护需要防止被反编译的源代码呢?混淆(obfuscate)技术注意:用obfuscate防盗版是根本不可能,连汇…...
从事计算机视觉需要掌握哪些知识
目录 基础数学知识 计算机科学基础 传统计算机视觉知识 机器学习与深度学习知识 其他知识 计算机视觉是一门让计算机从图像或视频中获取有意义信息的跨学科领域,从事该领域需要掌握多方面的知识,以下详细介绍: 基础数学知识 线性代数 &…...
Android Studio 中 Drawable 详细全解
文章目录 一、Drawable 概述二、Drawable 类型详解1. 位图 Drawable (BitmapDrawable)2. 矢量 Drawable (VectorDrawable)3. 形状 Drawable (ShapeDrawable)4. 图层 Drawable (LayerDrawable)5. 状态列表 Drawable (StateListDrawable)6. 级别列表 Drawable (LevelListDrawable…...
【实战中提升自己】内网安全部署之端口隔离与MAC地址认证
1 1拓扑 「模拟器、工具合集」复制整段内容 链接:https://docs.qq.com/sheet/DV0xxTmFDRFVoY1dQ?tab7ulgil 1 端口隔离技术部署 [boss]port-group 1 [boss-port-group-1]port-isolate enable 说明:这里有几个地方不需要部署…...