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";…...
使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...

