刷题25-重排链表
重排链表
解题思路:通过观察链表可以发现,把链表一分为二,后半段链表反转,然后两个链表穿插连接,当链表的节点总数是奇数时,要保证链表的前半段比后半段多一个节点。
关于把链表一分为二,可以采用定义快慢指针的做法,快指针每次走两步,慢指针每次走一步,当快指针走到末尾时,满指针也走到了中间节点。
重新定义反转函数reverseList()
代码如下:
class Solution {public void reorderList(ListNode head) {ListNode dummy=new ListNode(0);//创建头节点dummy.next=head;ListNode fast=dummy;//定义快指针,每次走两步ListNode slow=dummy;//定义慢指针,每次走一步while(fast!=null&&fast.next!=null) {slow=slow.next;fast=fast.next;if(fast.next!=null) {fast=fast.next;}}//循环结束,慢指针正好走到前半段链表的末尾//当链表节点总数是奇数时,确保链表的前半段比后半段多一个节点ListNode temp=slow.next;//后半段链表的开头节点slow.next=null;//此时head代表链表的前半段,temp代表链表的后半段//dummy代表有空头节点的head链表的前半段link(head,reverseList(temp),dummy);}private ListNode reverseList(ListNode head) {ListNode pre=null;ListNode cur=head;while(cur!=null) {ListNode next=cur.next;cur.next=pre;//反转链表 第一步,第一个节点的后面是null节点pre=cur;cur=next;}return pre;}public void link(ListNode node1,ListNode node2,ListNode head) {ListNode pre=head;//带头结点while(node1!=null&&node2!=null) {ListNode temp=node1.next;pre.next=node1;node1.next=node2;pre=node2;node1=temp;node2=node2.next;}if(node1!=null) {pre.next=node1;} }
}
第二种方法:使用双端队列deque
deque做队列使用时,继承了Queue的接口,所以插入元素操作可以使用Queue的用法offer()或者相当于deque的从队尾插入元素offerLast()
offerLast(): 向队尾插入元素,如果插入成功返回true,否则返回false
removeFirst(): 返回并移除队头元素,如果该元素是null,则发生NoSuchElementException
removeLast(): 返回并移除队尾元素,如果该元素是null,则发生NoSuchElementException
代码如下:
class Solution {public void reorderList(ListNode head) {Deque<ListNode> deque=new LinkedList<>();ListNode cur=head;while(cur!=null) {deque.offer(cur);//双端队列入队cur=cur.next;}cur=head;//指针又回到头节点for(int i=0;!deque.isEmpty();i++,cur=cur.next,cur.next=null) {cur.next=i%2==0?deque.removeFirst():deque.removeLast();}
}
}
Deque的用法:
1.Deque的介绍
public interface Deque<E> extends Queue<E>
Deque是一个双端队列接口,继承来自Queue接口
Deque的实现类是LinkedList、ArrayDeque、LinkedBlockingDeque,但是一般常用LinkedList实现接口。
(1)一般场景
LinkedList 大小可变的链表双端队列,允许元素为null
ArrayDeque 大小可变的数组双端队列,不允许null
(2)并发场景
LinkedBlockingDeque如果队列为空时,获取操作将会阻塞,知道有元素添加
定义的函数
Deque实现了双向队列,队列,和栈的功能
普通队列
Deque<E> deque=new LinkedList<>()
双端队列
Deque<E> deque=new LinkedList<>()
堆栈
Deque<E> deque=new LinkedList<>()
相关文章:

刷题25-重排链表
重排链表 解题思路:通过观察链表可以发现,把链表一分为二,后半段链表反转,然后两个链表穿插连接,当链表的节点总数是奇数时,要保证链表的前半段比后半段多一个节点。 关于把链表一分为二,可以…...

VHDL-延迟模型-惯性延迟与传输延迟
目录 1,惯性延时 2,传输延时 信号通过元件都会有延迟,延迟时间的计算是逻辑仿真的重要功能。考虑延迟信息得到的仿真输出波形可以更精确地反映实际电路的情况。针对元件的延时,人们根据需要建立了一些用的延时模型,这…...

2023年美赛(MCM/ICM)简介
2023年美赛将要如期开赛,这里为了 让大家对今年的美赛有一个直接 客观的了解。对2023年美赛(MCM/ICM)进行一下简要的介绍。相关资料大家可以查看另一篇文章一、竞赛时间February 16-20, 2023开赛时间 北京时间 17号(本周五) 6:00结束时间 北京时间 21号(…...

5min完成linux环境Jenkins的安装
5min搞定linux环境Jenkins的安装安装Jenkinsstep1: 使用wget 命令下载Jenkinsstep2、创建Jenkins日志目录并运行jekinsstep3、访问jenkins并解锁jenkins,安装插件以及创建管理员用户step4、到此,就完成了Finish、以上步骤中遇到的问题1、 jenkins启动不了…...
华为OD机试 - 字母计数(Python)| 真题+思路+考点+代码+岗位
字母计数 题目 给出一个只包含字母的字符串, 不包含空格,统计字符串中各个子字母(区分大小写)出现的次数, 并按照字母出现次数从大到小的顺序输出各个字母及其出现次数 如果次数相同,按照自然顺序排序,且小写字母在大写字母之前 输入 输入一行仅包含字母的字符串 输出 按…...

DENSE 数据集 - STF 数据集(CVPR 2020)
DENSE 数据集 - STF 数据集 - Seeing Through Fog Without Seeing Fog: Deep Multimodal Sensor Fusion in Unseen Adverse Weather(CVPR 2020)摘要1. 引言2. 相关工作3. 多模式恶劣天气数据集3.1 多模态传感器设置3.2 记录4. 自适应深度融合4.1 自适应多…...
华为OD机试 - 静态扫描最优成本(Python)| 真题+思路+考点+代码+岗位
静态扫描最优成本 题目 静态扫描快速识别源代码的缺陷,静态扫描的结果以扫描报告作为输出: 文件扫描的成本和文件大小相关,如果文件大小为 N ,则扫描成本为 N 个金币扫描报告的缓存成本和文件大小无关,每缓存一个报告需要 M 个金币扫描报告缓存后,后继再碰到该文件则不…...

【ns-3】零基础安装教程
文章目录前言1. 安装虚拟机及Ubuntu2. 安装依赖库3. 下载ns-34. 构建ns-3前言 近期因工作需要开始接触ns-3。作者零基础,从零开始顺利完成了ns-3的安装。本篇为ns-3安装过程记录贴或针对小白的零基础教程。 本篇内容所使用到的软件版本信息如下:VMware…...
华为OD机试 - 新学校选址(Python)| 真题+思路+考点+代码+岗位
新学校选址 题目 为了解新学期学生暴涨的问题,小乐村要建立所新学校 考虑到学生上学安全问题,需要所有学生家到学校的距离最短. 假设学校和所有学生家都走在一条直线之上,请问学校建立在什么位置, 能使得到学校到各个学生家的距离和最短 输入 第一行: 整数 n 取值范围 [1,1…...
华为OD机试 - 最长合法表达式(Python)| 真题+思路+考点+代码+岗位
最长合法表达式 题目 提取字符串中的最长合法简单数学表达式, 字符串长度最长的,并计算表达式的值。 如果没有返回0. 简单数学表达式只能包含以下内容: 0-9数字,符号+-* 说明: 所有数字,计算结果都不超过long如果有多个长度一样的,请返回第一个表达式的结果数学表达式…...

夭寿啦!我的网站被攻击了了735200次还没崩
记得有一个看到鱼皮的网站被攻击,那时候我只是一个小小号,还在调侃,没想到我居然也有那么一天! 突袭 一个风和日丽中午,我正在和同事吃饭,一个内存oom,我的小破站崩溃了。 虽然天天被攻击吧&a…...

Java 反射深入浅出
Java 反射深入浅出📈 反射的概述:📑 Java Reflection(反射) 被视为动态语言的关键,Java并不是动态语言,但因为反射Java可以被称为准动态语言 反射机制允许程序在执行期 借助于Reflection API取得任何类的内部信息&a…...

Windows系统,安装RabbitMQ
官网地址:https://rabbitmq.com 版本:RabbitMQ 3.10.7 (1)查看支持的Erlang版本:https://rabbitmq.com/which-erlang.html (2)下载支持的的erlang版本:https://github.com/erlang/…...
代码随想录第十二天(232)
文章目录232. 用栈实现队列补充知识——Deque232. 用栈实现队列 答案思路: 在push数据的时候,只要数据放进输入栈就好,但在pop的时候,操作就复杂一些,输出栈如果为空,就把进栈数据全部导入进来࿰…...
自动生成代码工具配置文件及技术点详解
引言 之前发过一篇文章关于自动生成代码的项目。有小伙伴私信说要讲一下具体的思路与配置信息,现在满足一下大家的好奇! 配置信息 generator.properties配置文件中的具体内容可以看下方的配置信息说明、对应关系 key值对应含义mainPath主目录package…...

【C++】类与对象(三)
前言 本章我们接替前一章继续深入理解类的默认成员函数,赋值重载,取地址重载,及const取地址操作符重载 但是在讲剩下的三个默认成员函数之前,我们要先来了解运算符重载,因为赋值重载,取地址重载,…...
华为OD机试 - 任务混部 (Python)| 真题+思路+考点+代码+岗位
任务混部 题目 新型冠状病毒疫情的肆虐,使得家在武汉的大壮不得不思考自己家和附近定点医院的具体情况。 经过一番调查, 大壮明白了距离自己家最近的定点医院有两家。其中医院 A 距离自己的距离是 X 公里,医院 B 距离自己的距离是 Y 公里。 由于武汉封城,公交停运,私家…...
Gin 如何编写一个接收文件的 HTTP 接口
文章目录1.前言2.ChatGPT 的回答3.小结参考文献1.前言 以前遇到编程类的问题,第一时间想到的是 Google,而现在我会问 ChatGPT。 2.ChatGPT 的回答 比如 Gin 如何编写一个接收文件的 HTTP 接口,感受下 ChatGPT 工整有序的回答吧。 使用 Gin…...
连续子数组的最大和 (贪心,动态规划) AcWing(JAVA)
输入一个 非空 整型数组,数组里的数可能为正,也可能为负。 数组中一个或连续的多个整数组成一个子数组。 求所有子数组的和的最大值。 要求时间复杂度为 O(n)。 数据范围: 数组长度 [1,1000]。 数组内元素取值范围 [−200,200][−200,200]。 …...
华为OD机试 - 括号检查(Python)| 真题+思路+考点+代码+岗位
括号检查 题目 现有一字符串 仅由(,),{,},[,]六种括号组成 若字符串满足以下条件之一,则为无效字符串 任意类型的左右括号数量不相等存在未按正确顺序(先左后右)闭合的括号, 输出括号的最大嵌套深度 若字符串无效则输出0 0 <= 字符串长度 <= 100000输入 一个只包括(…...

JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...

MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...

学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...
第7篇:中间件全链路监控与 SQL 性能分析实践
7.1 章节导读 在构建数据库中间件的过程中,可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中,必须做到: 🔍 追踪每一条 SQL 的生命周期(从入口到数据库执行)&#…...