力扣143重排链表

143. 重排链表

给定一个单链表 L 的头节点 head ,单链表 L 表示为:

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

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

image

输入:head = [1,2,3,4]
输出:[1,4,2,3]

image

输入:head = [1,2,3,4,5]
输出:[1,5,2,4,3]

解:

最初我是这样来写的:

class Solution {public void reorderList(ListNode head) {if (head == null || head.next == null) return;List<ListNode> list = new ArrayList<>();ListNode node = head;while (node != null) {list.add(node);node = node.next;}int i = 0, j = list.size() - 1;while (i < j) {list.get(i).next = list.get(j);i++;list.get(j).next = list.get(i);j--;}list.get(i).next = null; }
}

观看题解后发现,好嘛,还能这么干。

image

那我们就很明确了,先找到中间节点、再将后半部分反转、接下来交叉合并。

寻找链表的中间节点

这一步呢十分的简单,只需要一个快慢指针就可以解决。

设置一个慢指针一次走一步,设置一个快指针一次走两步。最后快指针走到头,慢指针的位置就是节点的中间位置了。

public ListNode findMidNode(ListNode head){ListNode fast = head;ListNode slow = head;while(fast.next != null && fast.next.next != null){slow = slow.next;fast = fast.next.next;}return slow;}

但是这时候有个问题,代码中判断条件上判断了两次fast。fast.next != null && fast.next.next != null

Q:这是为什么呢?

A:引入如果不检查下一个节点是否为空,直接跳两步,就很可能造成空指针异常

快指针每次移动两步(fast = fast.next.next),但移动的前提是:
第一步:fast.next 必须存在(否则无法访问 fast.next.next)。
第二步:fast.next.next 必须存在(否则第二步会指向 null)。
因此,循环条件必须确保这两个节点均非空,才能让快指针安全跳跃。
并且!顺序一定要先判断fast.next再判断fast.next.next

反转链表

public ListNode reverseList(ListNode head) {ListNode pre = null;ListNode cur = head;while(cur != null){ListNode temp = cur.next; //防止断层,先存起来cur.next = pre; //指向前一个,反转//进行下一次循环pre = cur; //下一次循环中,pre为当前元素cur = temp; // 下一次循环中,cur为当前元素的下一个。为什么不用cur.next呢?因为我们进行了反转操作,所以找不到下个了,这也是我们之前暂存cur.next的原因。}return pre;}

反转链表也比较好理解,重要的就是要存下来下一个节点

image

首先我们来想,反转链表不就是1指向null,2指向1,3指向2吗?

所以直接让pre = null,cur =1

反转不就是cur.next = pre (1->null)

那接下来呢?我们想一想,接下来是不是就应该让2指向1了

好那就让pre = 1,cur = 2

反转不也是cur.next = pre(2->1)

没问题吧,那我们来解决pre和cur是怎么变成1和2的。

pre=1,这个并不难,让pre = cur(在第一步cur=1的时候)就可以解决了
那cur=2呢?2是我们正常链表中1的下一个也就是1.next = 2。但是我们在上面已经把1和2切断了。链表变成了1->null 2->3->4->5

那我们是不是可以在一开始可以用一个ListNode先暂存起来2,也就是1.next

ok那我们来梳理一下,核心代码是不是就出来了

ListNode temp = cur.next; //防止断层,先存起来
cur.next = pre; //指向前一个,反转
//进行下一次循环的赋值
pre = cur; //下一次循环中,pre为当前元素
cur = temp; // 下一次循环中,cur为当前元素的下一个。为什么不用cur.next呢?因为我们进行了反转操作,所以找不到下个了,这也是我们之前暂存cur.next的原因。

交叉合并

交叉合并的代码就很简单了

public void mergeList(ListNode l1,ListNode l2){ListNode l1t;ListNode l2t;while (l1 != null && l2 != null) {l1t = l1.next;l2t = l2.next;l1.next = l2;l1 = l1t;l2.next = l1;l2 = l2t;}}

PixPin_2025-03-16_11-58-30

第一步我们是不是直接l1.next=l2即可。也就是1->5

那接下来,我们怎么怎么让l1指向2呢?

所以我们在前面需要暂存temp1 = l1.next

让l1 = temp1;接下来l2.next = l1就可以了

那l2又怎么指向4呢?和前面一样temp2 = l2.next,l2 = temp2即可

所以也就有了我们上面的核心代码

l1t = l1.next;
l2t = l2.next;l1.next = l2;
l1 = l1t;l2.next = l1;
l2 = l2t;

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/34597.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

wow-rag:task3-初步体验问答引擎

做RAG需要自己准备一个txt文档&#xff0c;新建一个docs文件夹&#xff0c;放进去。例如&#xff0c;这里放了一个./docs/问答手册.txt # 从指定文件读取&#xff0c;输入为List from llama_index.core import SimpleDirectoryReader,Document documents SimpleDirectoryRead…

bgp服务器是什么意思

一、基础概念 ‌BGP服务器‌&#xff08;Border Gateway Protocol Server&#xff09;指通过 ‌边界网关协议&#xff08;BGP&#xff09;‌ 实现 ‌多运营商线路智能调度‌ 的服务器&#xff0c;能够自动选择最优路径连接不同网络&#xff08;如电信、联通、移动&#xff09;…

AtCoder Beginner Contest 397(ABCDE)

目录 A - Thermometer 翻译&#xff1a; 思路&#xff1a; 实现&#xff1a; B - Ticket Gate Log 翻译&#xff1a; 思路&#xff1a; 实现&#xff1a; C - Variety Split Easy 翻译&#xff1a; 思路&#xff1a; 实现&#xff1a; D - Cubes 翻译&#xff1a…

unserialize3 [有难度,序列化反序列化知识点]

详情: 地址:https://adworld.xctf.org.cn/challenges/list (unserialize3) 看到题目名称是反序列化 代码审计 <?php class xctf{// 定义一个公有属性$flag&#xff0c;通常CTF题目中需要获取该属性值public $flag 111; // 此处为示例值&#xff0c;实际可能为真实flag/*…

【Linux-传输层协议TCP】TCP协议段格式+确认应答+超时重传+连接管理机制(三次握手、四次挥手、理解TIME_WAIT + CLOSE_WAIT)

TCP协议 TCP全称为“传输控制协议&#xff08;Transmission Control Protocol&#xff09;”人如其名&#xff0c;要对数据的传输进行一个详细的控制。 1.TCP协议段格式 下面是TCP报头各个字段的表格形式&#xff1a; 字段名称字段大小描述源端口16位发送端TCP端口号。目的端…

《AI大模型趣味实战》No2 : 快速搭建一个漂亮的AI家庭网站-相册/时间线/日历/多用户/个性化配色(中)

快速搭建一个漂亮的AI家庭网站-相册/时间线/日历/多用户/个性化配色(中) 摘要 在上一篇文章中&#xff0c;我们介绍了如何搭建一个基础的家庭网站&#xff08;V1.0版本&#xff09;&#xff0c;包含了用户管理、相册管理、时间线和日历等功能。本文将继续深入&#xff0c;详细…

React(二):JSX语法解析+综合案例

事件绑定 this绑定方式 问题&#xff1a;在事件执行后&#xff0c;需获取当前类的对象中相关属性&#xff0c;此时需要this——当打印时&#xff0c;发现this为undefined,这又是为啥&#xff1f; 假设有一个btnClick函数&#xff0c;但它并不是我们主动调用的&#xff0c;而是…

One of the configured repositories failed (未知), and yum doesn‘t have enough cached data to continue

centos操作系统运行yum命令是出现如下报错&#xff1a; 解决办法&#xff1a; 由于CentOS的源地址内容已移除&#xff0c;CentOS 操作系统结束了生命周期&#xff0c;源地址内容已移除。 只需要将它的base源换成其他可用源&#xff0c;我这里将它换成了阿里的base源 备份原来…

【蓝图使用】绘制mesh顶点的法线

文章目录 绘制法线Normal准备工作UE5资源制作蓝图制作 参考 绘制法线Normal 参考[1]打算用蓝图走一遍渲染管线&#xff0c;还是可以的 准备工作 Blender制作一个三个顶点的模型 要不要材质无所谓&#xff0c;就一个三个顶点的mesh即可&#xff0c;参考[2] 找到一个法线贴…

202503执行jmeter压测数据库(ScyllaDB,redis,lindorm,Mysql)

一、Mysql 1 、 准备MySQL 连接内容 2 、 下载连接jar包 准备 mysql-connector-java-5.1.49.jar 放到 D:\apache-jmeter-5.6.3\lib\ext 目录下面; 3 、 启动jmeter ,配置脚本 添加线程组---》JDBC Connection Configuration---》JDBC Request---》查看结果树。 1)测…

f-string高级字符串格式化与string Template()

f-string 高级字符串格式化 f-string无法替换带有${name}的字符串&#xff0c;会保留\$ def test_fstring():"""f-string&#xff0c;高级字符串格式化的方式"""s "my name is {name}".format(name李白)print(s)# 无法替换$s &quo…

【Java 优选算法】分治-归并排序

欢迎关注个人主页&#xff1a;逸狼 创造不易&#xff0c;可以点点赞吗~ 如有错误&#xff0c;欢迎指出~ 数组分块如二叉树的前序遍历, 而归并排序就如二叉树的后序遍历 912. 排序数组 解法 使用归并算法 根据中间点划分区间, mid (right left ) / 2将左右区间排序合并两个有…

docker入门篇

使用docker可以很快部署相同的环境,这也是最快的环境构建,接下来就主要对docker中的基础内容进行讲解.Docker 是一个用于开发、交付和运行应用程序的开源平台&#xff0c;它可以让开发者将应用程序及其依赖打包到一个容器中&#xff0c;然后在任何环境中运行这个容器&#xff0…

Learning vtkjs之ContourLoopExtraction

过滤器 等高线轮廓提取 介绍 这个过滤器可以获取一个cut的相交的循环的线&#xff0c;目前这个案例cut是一个平面&#xff0c;应该是可以支持更多隐式公式 效果 可以设置这个平面的原点Origin 法线方向Normal&#xff0c;然后就可以求交了 核心代码 需要实现这个代码主要…

如何高效解决 Java 内存泄漏问题方法论

目录 一、系统化的诊断与优化方法论 二、获取内存快照&#xff1a;内存泄漏的第一步 &#xff08;一&#xff09;自动生成 Heap Dump &#xff08;二&#xff09;手动生成 Heap Dump 三、导入分析工具&#xff1a;MAT 和 JProfiler &#xff08;一&#xff09;MAT (Memor…

新手村:数据预处理-异常值检测方法

机器学习中异常值检测方法 一、前置条件 知识领域要求编程基础Python基础&#xff08;变量、循环、函数&#xff09;、Jupyter Notebook或PyCharm使用。统计学基础理解均值、中位数、标准差、四分位数、正态分布、Z-score等概念。机器学习基础熟悉监督/无监督学习、分类、聚类…

大模型-提示词调优

什么是提示词 提示词&#xff08;Prompt&#xff09;在大模型应用中扮演着关键角色&#xff0c;它是用户输入给模型的一段文本指令 。简单来说&#xff0c;就是我们向大模型提出问题、请求或描述任务时所使用的文字内容。例如&#xff0c;当我们想让模型写一篇关于春天的散文&a…

VS2022输入 scanf 报错解决方法

1.第一种解决办法&#xff08;不推荐&#xff09; •将 scanf 替换为 scanf_s •scanf_s 是VS提供的一个函数&#xff0c;scanf_s函数的使用和scanf是有区别的 •scanf_s 是VS提供的一个函数&#xff0c;其他的编译器可能不认识这个函数&#xff0c;那么我们所写的代码就存在跨…

鸿蒙开发-一多开发之媒体查询功能

在HarmonyOS中&#xff0c;使用ArkTS语法实现响应式布局的媒体查询是一个强大的功能&#xff0c;它允许开发者根据不同的设备特征&#xff08;如屏幕尺寸、屏幕方向等&#xff09;动态地调整UI布局和样式。以下是一个使用媒体查询实现响应式布局的实例&#xff1a; 1. 导入必要…

火语言RPA--列表项内容获取

【组件功能】&#xff1a;获取列表中某项数据内容 配置预览 配置说明 获取 获取数据方式 首项&#xff1a;列表第一条数据 末项&#xff1a;列表最后一条数据 随机项&#xff1a;随机获取列表中一条数据 指定索引项&#xff1a;根据索引获取列表对象中数据。 索引项目位置 …