刷题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输入 一个只包括(…...

linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
【Android】Android 开发 ADB 常用指令
查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...