Java【手撕链表】LeetCode 143. “重排链表“, 图文详解思路分析 + 代码
文章目录
- 前言
- 一、两数相加
- 1, 题目
- 2, 思路分析
- 2,1 找到中间结点
- 2.2, 逆序后半段链表
- 2.3, 合并两个链表
- 3, 代码
前言
各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你:
📕 JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等
📗 Java数据结构: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等
📘 JavaEE初阶: 多线程, 网络编程, TCP/IP协议, HTTP协议, Tomcat, Servlet, Linux, JVM等(正在持续更新)
对于链表题, 常用的技巧和操作是: 头插, 尾插, 快慢双指针, 傀儡节点
一、两数相加
1, 题目
OJ链接
题目规定不能改变链表里的值, 而是真正交换链表节点
2, 思路分析
首先, 按照题意画出重排之后的链表, 观察原链表和重排之后的链表有什么变化

只看橙色结点, 发现后半段链表是逆序的
至此 本题的思路就非常清晰了
- 1, 找到中间节点(快慢双指针)
- 2, 逆序后半段链表(傀儡头节点 + 头插)
- 3, 合并两个链表(傀儡头结点 + 双指针)
注意本题没有返回值, 所以第三步操作之后不是返回新的头结点, 而是要修改原链表的头结点 head 之后的结点的指向
2,1 找到中间结点
- 1, 定义 slow 和 fast 两个指针, 起始位置都指向头结点
- 2, slow 每次走一步, fast 每次走两步
- 3, 当 fast 为 null 或 fast.next 为 null 时退出循环

如果有奇数个结点, slow 刚好是中间结点, 如果是偶数个结点, slow 是偏右的中间节点
2.2, 逆序后半段链表
- 1, 定义一个傀儡节点 pHead
- 2, 定义一个 target 指针, target 就指向刚才的 slow
- 3, 定义一个 next 指针, 记录 target 的下一个结点
- 4, 循环遍历后半段链表, 依次头插到 pHead 所在的链表



此时 target 为 null, 逆序完成, 退出循环
这里有个 bug ! 在循环逆序链表之前应该
先断开原链表的前半段和后半段
否则逆序完成之后, 原链表并没有断开, 再执行第三步 (合并两个链表) 时就会发生死循环!
所以在第一步时应该定义一个 prev 指针, 记录 slow 结点的前一个结点, 找到中间结点后, 令prev.next = null
2.3, 合并两个链表
- 1, 定义一个傀儡节点 ret
- 2, 定义一个 cur1 指针, 指向原链表头结点 head
- 3, 定义一个 cur2 指针, 指向逆序后的链表的头结点
- 4, 定义一个 cur3 指针, 指向 ret
1, cur1 尾插到 cur3 后面

(此时 1 这个结点还指向 2 ), cur2 尾插到 cur3 后面

2, (此时 6 这个结点还指向 5 ), cur1 尾插到 cur3 后面,

(此时 2 这个结点还指向 3 ), cur2 尾插到 cur3 后面

3, (此时 5 这个结点还指向 4 ), cur1 尾插到 cur3 后面

cur2 尾插到 cur3 后面

4, 得到整个链表, 此时 head 结点还在, 并且 head 之后的结点链表结构已经被修改成功

在一次循环中, 先尾插 cur1, 再尾插 cur2, 循环条件设为 cur1 != null 即可
因为 : 如果链表是偶数个结点, 链表前半段和后半段长度相同, 如果链表是奇数个结点, 链表前半段比后半段少一个结点, 但没关系, 尾插时不会改变结点的的 next 域
3, 代码
public void reorderList(ListNode head) {if(head == null || head.next == null) {return;}// 1, 找到中间节点ListNode slow = head;ListNode fast = slow;ListNode prev = head;while(fast != null && fast.next != null) {prev = slow;slow = slow.next;fast = fast.next.next;}ListNode target = slow;prev.next = null;ListNode phead = new ListNode(0);ListNode cur = phead;// 2, 逆序后半个链表while(target != null) {ListNode next = target.next;target.next = cur.next;cur.next = target;target = next;}ListNode cur1 = head;ListNode cur2 = phead.next;ListNode ret = new ListNode(0);ListNode cur3 = ret;// 3, 合并链表while(cur1 != null){cur3.next = cur1;cur3 = cur3.next;cur1 = cur1.next;cur3.next = cur2;cur3 = cur3.next;cur2 = cur2.next;}}
相关文章:
Java【手撕链表】LeetCode 143. “重排链表“, 图文详解思路分析 + 代码
文章目录 前言一、两数相加1, 题目2, 思路分析2,1 找到中间结点2.2, 逆序后半段链表2.3, 合并两个链表 3, 代码 前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: 📕 JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管…...
C语言 cortex-A7核 按键中断 实验【重点】
一、KEY1 include/key.h #ifndef __KEY_H__ #define __KEY_H__#include "stm32mp1xx_rcc.h" #include "stm32mp1xx_gpio.h" #include "stm32mp1xx_exti.h" #include "stm32mp1xx_gic.h"//RCC/GPIO章节初始化 void hal_rcc_gpio_init…...
freertos中函数调用和启动第一个任务(栈相关!!!!!!)
本内容仅就一些较难理解的点讲解,请结合其它文章实用 在函数调用时,m3的处理器使用r0-r3共四个寄存器传参,其余的使用栈传参。 但是,如果传入的参数是全局变量,则不需传参,因为全局变量在函数内部是可见的…...
【PHP】如何关闭buffer实时输出内容到前端
前言 默认情况下,我们在PHP里使用echo等函数输出的内容,是不会马上发送给前端的,原因是有 buffer 的存在,buffer又分两处,一处是PHP本身的buffer,另一处是Nginx的buffer。只有当buffer满了之后,…...
Scala第二章节
Scala第二章节 scala总目录 章节目标 掌握变量, 字符串的定义和使用掌握数据类型的划分和数据类型转换的内容掌握键盘录入功能理解Scala中的常量, 标识符相关内容 1. 输出语句和分号 1.1 输出语句 方式一: 换行输出 格式: println(里边写你要打印到控制台的数据);方式二…...
Spring修炼之路(2)依赖注入(DI)
一、概念 依赖注入(Dependency Injection,DI)。 测试pojo类 : Address.java 依赖 : 指Bean对象的创建依赖于容器 . Bean对象的依赖资源 . 注入 : 指Bean对象所依赖的资源 , 由容器来设置和装配 . 二、 注入方式 2.1构造器注入 我们在之前的案例已经…...
编写Android.mk / Android.bp 引用三方 jar 包,aar包,so 库
一.前言 在Android10之后,所有项目工程中,官方推荐使用Android.bp去编译构建,以前使用Android.mk构建的项目随着版本迭代升级,慢慢需要变更为Android.bp, 两者的语法都需要去了解并熟练使用。 笔者之前写过Android.mk的…...
【kylin】【ubuntu】搭建本地源
文章目录 一、制作一个本地源仓库制作ubuntu本地仓库制作kylin本地源 二、制作内网源服务器ubuntu系统kylin系统 三、使用内网源ubuntukylin 一、制作一个本地源仓库 制作ubuntu本地仓库 首先需要构建一个本地仓库,用来存放软件包 mkdir -p /path/to/localname/pac…...
为什么 Go 语言 struct 要使用 tags
在 Go 语言中,struct 是一种常见的数据类型,它可以用来表示复杂的数据结构。在 struct 中,我们可以定义多个字段,每个字段可以有不同的类型和名称。 除了这些基本信息之外,Go 还提供了 struct tags,它可以用…...
WebGL笔记:WebGL中JS与GLSL ES 语言通信,着色器间的数据传输示例:用鼠标控制点位
用鼠标控制点位 <canvas id"canvas"></canvas><!-- 顶点着色器 --> <script id"vertexShader" type"x-shader/x-vertex">attribute vec4 a_Position;void main() {// 点位gl_Position a_Position;// 尺寸gl_PointSize…...
算法 主持人调度-(双指针+贪心)
牛客网: BM96 题目: 一个主持人只能参加一个活动,至少需要多少主持人 思路: 对start, end排序从小到大;初始化指针l, r 0, 0;start[r]< end[l]时需要累加人数同时r,否则l,r同时移动;直至不再满中l<n &&am…...
Elasticsearch 集群时的内部结构是怎样的?
Apache Lucene : Flush, Commit Elasticsearch 是一个基于 Apache Lucene 构建的搜索引擎。 它利用 Lucene 的倒排索引、查询处理和返回搜索结果等功能来执行搜索。 它还扩展了 Lucene 的功能,添加分布式处理功能以支持大型数据集的搜索。 让我们看一下 Apache Luc…...
IoTDB 在国际数据库性能测试排行榜中位居第一?测试环境复现与流程详解第一弹!...
最近我们得知,Apache IoTDB 多项性能表现位居 benchANT 时序数据库排行榜(Time Series: DevOps)性能排行第一名!(榜单地址:https://benchANT.com/ranking/database-ranking) benchANT 位于德国&…...
react项目优化
随着项目体积增大,打包的文件体积会越来越大,需要优化,原因无非就是引入的第三方插件比较大导致,下面我们先介绍如何分析各个文件占用体积的大小。 1.webpack-bundle-analyzer插件 如果是webpack作为打包工具的项目可以使用&…...
青藏高原1-km分辨率生态环境质量变化数据集(2000-2020)
青藏高原平均海拔4000米以上,人口1300万,是亚洲九大河流的源头,为超过15亿人口提供淡水、食物和其他生态系统服务,被誉为地球第三极和亚洲水塔。然而,在该地区的人与自然的关系的研究是有限的,尤其是在精细…...
Nature Communications | 张阳实验室:端到端深度学习实现高精度RNA结构预测
RNA分子是基因转录的主要执行者,也是细胞运作的隐形功臣。它们在基因表达调控、支架构建以及催化活性等多个生命过程中都扮演着关键角色。虽然RNA如此重要,但由于实验数据的缺乏,准确预测RNA 的三维空间结构仍然是目前计算生物学面临的重大挑…...
提升您的Mac文件拖拽体验——Dropzone 4 for mac
大家都知道,在Mac上进行文件拖拽是一件非常方便的事情。然而,随着我们在工作和生活中越来越多地使用电脑,我们对于这个简单操作的需求也越来越高。为了让您的文件拖拽体验更加高效和便捷,今天我们向大家介绍一款强大的工具——Dro…...
Vue之transition组件
Vue提供了transition组件,使用户可以更便捷地添加过渡动画效果。 transition组件 transition组件也是一个抽象组件,并不会渲染出真实dom。Vue会在其第一个真实子元素上添加过渡效果。 props render 这里将render分为两部分,第一部分界定真…...
lenovo联想笔记本电脑ThinkPad X13 AMD Gen2(20XH,20XJ)原装出厂Windows10系统镜像
联想原厂Win10系统,自带所有驱动、出厂主题壁纸、系统属性联想LOGO专属标志、Office办公软件、联想电脑管家等预装程序 链接:百度网盘 请输入提取码 提取码:dolg 适用于型号:20XL,20XJ,20XG,21A1,20XK,20XH,20XF,21A0 所需要…...
php导出cvs,excel打开数字超过16变科学计数法
今天使用php导出cvs,在excel中打开,某一个字段是数字,长度高于16位结果就显示科学计数法 超过15位的话从第16位开始就用0代替了 查询了半天总算解决了就是在后面加上"\t" $data[$key][1] " ".$value[1]."\t";…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...
Appium下载安装配置保姆教程(图文详解)
目录 一、Appium软件介绍 1.特点 2.工作原理 3.应用场景 二、环境准备 安装 Node.js 安装 Appium 安装 JDK 安装 Android SDK 安装Python及依赖包 三、安装教程 1.Node.js安装 1.1.下载Node 1.2.安装程序 1.3.配置npm仓储和缓存 1.4. 配置环境 1.5.测试Node.j…...
OPENCV图形计算面积、弧长API讲解(1)
一.OPENCV图形面积、弧长计算的API介绍 之前我们已经把图形轮廓的检测、画框等功能讲解了一遍。那今天我们主要结合轮廓检测的API去计算图形的面积,这些面积可以是矩形、圆形等等。图形面积计算和弧长计算常用于车辆识别、桥梁识别等重要功能,常用的API…...
__VUE_PROD_HYDRATION_MISMATCH_DETAILS__ is not explicitly defined.
这个警告表明您在使用Vue的esm-bundler构建版本时,未明确定义编译时特性标志。以下是详细解释和解决方案: 问题原因: 该标志是Vue 3.4引入的编译时特性标志,用于控制生产环境下SSR水合不匹配错误的详细报告1使用esm-bundler…...
以太网PHY布局布线指南
1. 简介 对于以太网布局布线遵循以下准则很重要,因为这将有助于减少信号发射,最大程度地减少噪声,确保器件作用,最大程度地减少泄漏并提高信号质量。 2. PHY设计准则 2.1 DRC错误检查 首先检查DRC规则是否设置正确,然…...

