【LeetCode 算法】Reorder List 重排链表
文章目录
- Reorder List 重排链表
- 问题描述:
- 分析
- 代码
- Tag
Reorder List 重排链表
问题描述:
给定一个单链表 L 的头节点 head ,单链表 L 表示为:
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
链表的长度范围为 [ 1 , 5 ∗ 1 0 4 ] 1 < = n o d e . v a l < = 1000 链表的长度范围为 [1, 5 * 10^4]\\ 1 <= node.val <= 1000 链表的长度范围为[1,5∗104]1<=node.val<=1000
分析
仔细观察可以发现,最终的链表是呈现交替穿插的。
所以最简单的方式就是双端队列。
将所有节点依次入队,然后分别从2端点取节点,完成链接,然后继续从队列中取节点,补在之前的节点后面。
时间复杂度 O ( N ) O(N) O(N) ,空间复杂度 O ( N ) O(N) O(N).
只要熟悉双端队列,会操作链表节点插入,基本就可以。
还有一种思路是空间为 O ( 1 ) O(1) O(1)的。可以将链表拆成2段,然后将后段反转,然后进行合并。
所以需要知道从哪里拆,可以使用快慢指针,或者是简单遍历计数。还要知道如何反转链表,可以递归,或者是头插,或者是顺序逆转。
时间复杂度 O ( N ) O(N) O(N) ,空间复杂度 O ( 1 ) O(1) O(1).
代码
Pointer+Reverse+Merge
public void reorderList(ListNode head) {if(head==null||head.next==null) return ;ListNode h1 = new ListNode(-1);h1.next = head;ListNode f = h1,s = h1;while(f!=null&&f.next!=null){s = s.next;f = f.next.next;}ListNode h2 = new ListNode(-1);h2.next = s.next;s.next = null; // break listListNode p = h2.next;h2.next = null;while(p!=null){ListNode t = p;p = p.next;t.next = h2.next;h2.next = t;} ListNode h3 = new ListNode(-1);ListNode p1 = h1.next,p2 = h2.next,p3 = h3; while(p1!=null){if(p1!=null){p3.next = p1;p1 = p1.next;p3 = p3.next; }if(p2!=null){p3.next = p2;p2 = p2.next;p3 = p3.next;}}return;}
时间复杂度 O ( N ) O(N) O(N)
空间复杂度 O ( 1 ) O(1) O(1)
Tag
LinkedList
Two Pointers
相关文章:
【LeetCode 算法】Reorder List 重排链表
文章目录 Reorder List 重排链表问题描述:分析代码PointerReverseMerge Tag Reorder List 重排链表 问题描述: 给定一个单链表 L 的头节点 head ,单链表 L 表示为: L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为&#…...
MQ面试题3
1、讲一讲Kafka与RocketMQ中存储设计的异同? Kafka 中文件的布局是以 Topic/partition ,每一个分区一个物理文件夹,在分区文件级别实现文件顺序写,如果一个Kafka集群中拥有成百上千个主题,每一个主题拥有上百个分区&am…...
【Linux命令200例】patch 用于将补丁文件应用到源码中
🏆作者简介,黑夜开发者,全栈领域新星创作者✌,阿里云社区专家博主,2023年6月csdn上海赛道top4。 🏆本文已收录于专栏:Linux命令大全。 🏆本专栏我们会通过具体的系统的命令讲解加上鲜…...
一起来学算法(邻接矩阵)
前言: 邻接矩阵是数学和计算机科学中常用的一种表示方式,用来表述有向图或无向图,一张图由一组顶点(或结点)和一组表组成,用邻接矩阵就能表示这些顶点间存在的边的关系 1.图的概念 对于图而言,…...
hadoop与HDFS交互
一、利用Shell命令与HDFS进行交互 在进行HDFS编程实践前,需要首先启动Hadoop。可以执行如下命令启动Hadoop: cd /usr/local/hadoop ./sbin/start-dfs.sh #启动hadoop Hadoop支持很多Shell命令,其中fs是HDFS最常用的命令,利用fs…...
MYSQL 分区如何指定不同存储路径(多块磁盘)
理论 可以针对分区表的每个分区指定存储路径,对于innodb存储引擎的表只能指定数据路径,因为数据和索引是存储在一个文件当中,对于MYISAM存储引擎可以分别指定数据文件和索引文件,一般也只有RANGE、LIST分区、sub子分区才有可能需要…...
安全加固服务器
根据以下的内容来加固一台Linux服务器的安全。 首先是限制连续密码错误的登录次数,由于RHEL8之后都不再使用pam_tally.so和pam_tally2.so,而是pam_faillock.so 首先进入/usr/lib64/security/中查看有什么模块,确认有pam_faillock.so 因为只…...
Linux 命令学习:
1. PS命令 ps 的aux和-ef区别 1、输出风格不同,展示的格式略有不同 两者的输出结果差别不大,但展示风格不同。aux是BSD风格,-ef是System V风格。 2、aux会截断command列,而-ef不会,当结合grep时这种区别会影响到结果 …...
牛客网Verilog刷题——VL54
牛客网Verilog刷题——VL54 题目答案 题目 实现一个深度为8,位宽为4bit的双端口RAM,数据全部初始化为0000。具有两组端口,分别用于读数据和写数据,读写操作可以同时进行。当读数据指示信号read_en有效时,通过读地址信号…...
学习系统编程No.34【线程同步之信号量】
引言: 北京时间:2023/7/29/16:34,一切尽在不言中,前几天追了几部电视剧,看了几部电影,刷了n个视屏,在前天我们才终于从这快乐的日子里恢复过来,然后看了两节课,也就是上…...
SolidUI社区-Snakemq 通信源码分析
背景 随着文本生成图像的语言模型兴起,SolidUI想帮人们快速构建可视化工具,可视化内容包括2D,3D,3D场景,从而快速构三维数据演示场景。SolidUI 是一个创新的项目,旨在将自然语言处理(NLP)与计算机图形学相…...
【大数据之Flume】四、Flume进阶之复制和多路复用、负载均衡和故障转移、聚合案例
1 复制和多路复用 (1)需求:使用 Flume-1 监控文件变动(可以用Exec Source或Taildir Source),Flume-1 将变动内容传递给 Flume-2(用Avro Sink传),(用Avro Sou…...
前端学习--vue2--插槽
写在前面: 这个用法是在使用组件和创建组件中 文章目录 介绍简单使用多个插槽省写默认/后备内容作用域插槽常用实例Element-ui的el-table 废弃用法slot attributeslot-scope attribute 介绍 我们在定义一些组件的时候,由于组件内文字想要自定义&#…...
使用 Docker Compose 部署 Redis Cluster 集群,轻松搭建高可用分布式缓存
Redis Cluster(Redis 集群)是 Redis 分布式解决方案的一部分,它旨在提供高可用性、高性能和横向扩展的功能。Redis Cluster 能够将多个 Redis 节点组合成一个分布式集群,实现数据分片和负载均衡,从而确保在大规模应用场…...
在Spring Boot框架中集成 Spring Security
在Spring Boot框架中集成 Spring Security 目录 技术介绍SpringSecurity的核心功能:SpringSecurity特点:具体实现 1、集成依赖2、修改spring security实现service.impl.UserDetailsServiceImpl类 代码1具体解释代码2具体解释 实现config.SecurityConfi…...
登月再进一步:Apollo自动驾驶的里程碑
前言 「作者主页」:雪碧有白泡泡 「个人网站」:雪碧的个人网站 「推荐专栏」: ★java一站式服务 ★ ★前端炫酷代码分享 ★ ★ uniapp-从构建到提升★ ★ 从0到英雄,vue成神之路★ ★ 解决算法,一个专栏就够了★ ★ 架…...
嵌入式一开始该怎么学?学习单片机
学习单片机: 模电数电肯定必须的,玩单片机大概率这两门课都学过,学过微机原理更好。 直接看野火的文档,芯片手册,外设手册。 学单片机不要纠结于某个型号,我认为stm32就OK,主要是原理和感觉。…...
Spring事件监听器ApplicationListener
目录 介绍 spirng启动后启动某方法 介绍 ApplicationEvent以及Listener是Spring为我们提供的一个事件监听、订阅的实现,内部实现原理是观察者设计模式,设计初衷也是为了系统业务逻辑之间的解耦,提高可扩展性以及可维护性。事件发布者并不需…...
安全学习DAY10_HTTP数据包
HTTP数据包 文章目录 HTTP数据包小节导图Request请求数据包结构Request请求方法(方式)请求头(Header)Response响应数据包结构Response响应数据包状态码状态码作用:部分状态码详解判断网站文件是否存在的状态码…...
云原生落地实践的25个步骤
一、什么是云原生? 云原生从字面意思上来看可以分成云和原生两个部分。 云是和本地相对的,传统的应用必须跑在本地服务器上,现在流行的应用都跑在云端,云包含了IaaS,、PaaS和SaaS。 原生就是土生土长的意思,我们在开始…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
