当前位置: 首页 > news >正文

刷题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-重排链表

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

VHDL-延迟模型-惯性延迟与传输延迟

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

2023年美赛(MCM/ICM)简介

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

5min完成linux环境Jenkins的安装

5min搞定linux环境Jenkins的安装安装Jenkinsstep1: 使用wget 命令下载Jenkinsstep2、创建Jenkins日志目录并运行jekinsstep3、访问jenkins并解锁jenkins&#xff0c;安装插件以及创建管理员用户step4、到此&#xff0c;就完成了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&#xff08;CVPR 2020&#xff09;摘要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。作者零基础&#xff0c;从零开始顺利完成了ns-3的安装。本篇为ns-3安装过程记录贴或针对小白的零基础教程。 本篇内容所使用到的软件版本信息如下&#xff1a;VMware…...

华为OD机试 - 新学校选址(Python)| 真题+思路+考点+代码+岗位

新学校选址 题目 为了解新学期学生暴涨的问题,小乐村要建立所新学校 考虑到学生上学安全问题,需要所有学生家到学校的距离最短. 假设学校和所有学生家都走在一条直线之上,请问学校建立在什么位置, 能使得到学校到各个学生家的距离和最短 输入 第一行: 整数 n 取值范围 [1,1…...

华为OD机试 - 最长合法表达式(Python)| 真题+思路+考点+代码+岗位

最长合法表达式 题目 提取字符串中的最长合法简单数学表达式, 字符串长度最长的,并计算表达式的值。 如果没有返回0. 简单数学表达式只能包含以下内容: 0-9数字,符号+-* 说明: 所有数字,计算结果都不超过long如果有多个长度一样的,请返回第一个表达式的结果数学表达式…...

夭寿啦!我的网站被攻击了了735200次还没崩

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

Java 反射深入浅出

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

Windows系统,安装RabbitMQ

官网地址&#xff1a;https://rabbitmq.com 版本&#xff1a;RabbitMQ 3.10.7 &#xff08;1&#xff09;查看支持的Erlang版本&#xff1a;https://rabbitmq.com/which-erlang.html &#xff08;2&#xff09;下载支持的的erlang版本&#xff1a;https://github.com/erlang/…...

代码随想录第十二天(232)

文章目录232. 用栈实现队列补充知识——Deque232. 用栈实现队列 答案思路&#xff1a; 在push数据的时候&#xff0c;只要数据放进输入栈就好&#xff0c;但在pop的时候&#xff0c;操作就复杂一些&#xff0c;输出栈如果为空&#xff0c;就把进栈数据全部导入进来&#xff0…...

自动生成代码工具配置文件及技术点详解

引言 之前发过一篇文章关于自动生成代码的项目。有小伙伴私信说要讲一下具体的思路与配置信息&#xff0c;现在满足一下大家的好奇&#xff01; 配置信息 generator.properties配置文件中的具体内容可以看下方的配置信息说明、对应关系 key值对应含义mainPath主目录package…...

【C++】类与对象(三)

前言 本章我们接替前一章继续深入理解类的默认成员函数&#xff0c;赋值重载&#xff0c;取地址重载&#xff0c;及const取地址操作符重载 但是在讲剩下的三个默认成员函数之前&#xff0c;我们要先来了解运算符重载&#xff0c;因为赋值重载&#xff0c;取地址重载&#xff0c…...

华为OD机试 - 任务混部 (Python)| 真题+思路+考点+代码+岗位

任务混部 题目 新型冠状病毒疫情的肆虐,使得家在武汉的大壮不得不思考自己家和附近定点医院的具体情况。 经过一番调查, 大壮明白了距离自己家最近的定点医院有两家。其中医院 A 距离自己的距离是 X 公里,医院 B 距离自己的距离是 Y 公里。 由于武汉封城,公交停运,私家…...

Gin 如何编写一个接收文件的 HTTP 接口

文章目录1.前言2.ChatGPT 的回答3.小结参考文献1.前言 以前遇到编程类的问题&#xff0c;第一时间想到的是 Google&#xff0c;而现在我会问 ChatGPT。 2.ChatGPT 的回答 比如 Gin 如何编写一个接收文件的 HTTP 接口&#xff0c;感受下 ChatGPT 工整有序的回答吧。 使用 Gin…...

连续子数组的最大和 (贪心,动态规划) AcWing(JAVA)

输入一个 非空 整型数组&#xff0c;数组里的数可能为正&#xff0c;也可能为负。 数组中一个或连续的多个整数组成一个子数组。 求所有子数组的和的最大值。 要求时间复杂度为 O(n)。 数据范围&#xff1a; 数组长度 [1,1000]。 数组内元素取值范围 [−200,200][−200,200]。 …...

华为OD机试 - 括号检查(Python)| 真题+思路+考点+代码+岗位

括号检查 题目 现有一字符串 仅由(,),{,},[,]六种括号组成 若字符串满足以下条件之一,则为无效字符串 任意类型的左右括号数量不相等存在未按正确顺序(先左后右)闭合的括号, 输出括号的最大嵌套深度 若字符串无效则输出0 0 <= 字符串长度 <= 100000输入 一个只包括(…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...