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

【LeetCode 算法】Reorder List 重排链表

文章目录

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,5104]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 重排链表问题描述&#xff1a;分析代码PointerReverseMerge Tag Reorder List 重排链表 问题描述&#xff1a; 给定一个单链表 L 的头节点 head &#xff0c;单链表 L 表示为&#xff1a; L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为&#…...

MQ面试题3

1、讲一讲Kafka与RocketMQ中存储设计的异同&#xff1f; Kafka 中文件的布局是以 Topic/partition &#xff0c;每一个分区一个物理文件夹&#xff0c;在分区文件级别实现文件顺序写&#xff0c;如果一个Kafka集群中拥有成百上千个主题&#xff0c;每一个主题拥有上百个分区&am…...

【Linux命令200例】patch 用于将补丁文件应用到源码中

&#x1f3c6;作者简介&#xff0c;黑夜开发者&#xff0c;全栈领域新星创作者✌&#xff0c;阿里云社区专家博主&#xff0c;2023年6月csdn上海赛道top4。 &#x1f3c6;本文已收录于专栏&#xff1a;Linux命令大全。 &#x1f3c6;本专栏我们会通过具体的系统的命令讲解加上鲜…...

一起来学算法(邻接矩阵)

前言&#xff1a; 邻接矩阵是数学和计算机科学中常用的一种表示方式&#xff0c;用来表述有向图或无向图&#xff0c;一张图由一组顶点&#xff08;或结点&#xff09;和一组表组成&#xff0c;用邻接矩阵就能表示这些顶点间存在的边的关系 1.图的概念 对于图而言&#xff0c;…...

hadoop与HDFS交互

一、利用Shell命令与HDFS进行交互 在进行HDFS编程实践前&#xff0c;需要首先启动Hadoop。可以执行如下命令启动Hadoop&#xff1a; cd /usr/local/hadoop ./sbin/start-dfs.sh #启动hadoop Hadoop支持很多Shell命令&#xff0c;其中fs是HDFS最常用的命令&#xff0c;利用fs…...

MYSQL 分区如何指定不同存储路径(多块磁盘)

理论 可以针对分区表的每个分区指定存储路径&#xff0c;对于innodb存储引擎的表只能指定数据路径&#xff0c;因为数据和索引是存储在一个文件当中&#xff0c;对于MYISAM存储引擎可以分别指定数据文件和索引文件&#xff0c;一般也只有RANGE、LIST分区、sub子分区才有可能需要…...

安全加固服务器

根据以下的内容来加固一台Linux服务器的安全。 首先是限制连续密码错误的登录次数&#xff0c;由于RHEL8之后都不再使用pam_tally.so和pam_tally2.so&#xff0c;而是pam_faillock.so 首先进入/usr/lib64/security/中查看有什么模块&#xff0c;确认有pam_faillock.so 因为只…...

Linux 命令学习:

1. PS命令 ps 的aux和-ef区别 1、输出风格不同&#xff0c;展示的格式略有不同 两者的输出结果差别不大&#xff0c;但展示风格不同。aux是BSD风格&#xff0c;-ef是System V风格。 2、aux会截断command列&#xff0c;而-ef不会&#xff0c;当结合grep时这种区别会影响到结果 …...

牛客网Verilog刷题——VL54

牛客网Verilog刷题——VL54 题目答案 题目 实现一个深度为8&#xff0c;位宽为4bit的双端口RAM&#xff0c;数据全部初始化为0000。具有两组端口&#xff0c;分别用于读数据和写数据&#xff0c;读写操作可以同时进行。当读数据指示信号read_en有效时&#xff0c;通过读地址信号…...

学习系统编程No.34【线程同步之信号量】

引言&#xff1a; 北京时间&#xff1a;2023/7/29/16:34&#xff0c;一切尽在不言中&#xff0c;前几天追了几部电视剧&#xff0c;看了几部电影&#xff0c;刷了n个视屏&#xff0c;在前天我们才终于从这快乐的日子里恢复过来&#xff0c;然后看了两节课&#xff0c;也就是上…...

SolidUI社区-Snakemq 通信源码分析

背景 随着文本生成图像的语言模型兴起&#xff0c;SolidUI想帮人们快速构建可视化工具&#xff0c;可视化内容包括2D,3D,3D场景&#xff0c;从而快速构三维数据演示场景。SolidUI 是一个创新的项目&#xff0c;旨在将自然语言处理&#xff08;NLP&#xff09;与计算机图形学相…...

【大数据之Flume】四、Flume进阶之复制和多路复用、负载均衡和故障转移、聚合案例

1 复制和多路复用 &#xff08;1&#xff09;需求&#xff1a;使用 Flume-1 监控文件变动&#xff08;可以用Exec Source或Taildir Source&#xff09;&#xff0c;Flume-1 将变动内容传递给 Flume-2&#xff08;用Avro Sink传&#xff09;&#xff0c;&#xff08;用Avro Sou…...

前端学习--vue2--插槽

写在前面&#xff1a; 这个用法是在使用组件和创建组件中 文章目录 介绍简单使用多个插槽省写默认/后备内容作用域插槽常用实例Element-ui的el-table 废弃用法slot attributeslot-scope attribute 介绍 我们在定义一些组件的时候&#xff0c;由于组件内文字想要自定义&#…...

使用 Docker Compose 部署 Redis Cluster 集群,轻松搭建高可用分布式缓存

Redis Cluster&#xff08;Redis 集群&#xff09;是 Redis 分布式解决方案的一部分&#xff0c;它旨在提供高可用性、高性能和横向扩展的功能。Redis Cluster 能够将多个 Redis 节点组合成一个分布式集群&#xff0c;实现数据分片和负载均衡&#xff0c;从而确保在大规模应用场…...

在Spring Boot框架中集成 Spring Security

在Spring Boot框架中集成 Spring Security 目录 技术介绍SpringSecurity的核心功能&#xff1a;SpringSecurity特点&#xff1a;具体实现 1、集成依赖2、修改spring security实现service.impl.UserDetailsServiceImpl类 代码1具体解释代码2具体解释 实现config.SecurityConfi…...

登月再进一步:Apollo自动驾驶的里程碑

前言 「作者主页」&#xff1a;雪碧有白泡泡 「个人网站」&#xff1a;雪碧的个人网站 「推荐专栏」&#xff1a; ★java一站式服务 ★ ★前端炫酷代码分享 ★ ★ uniapp-从构建到提升★ ★ 从0到英雄&#xff0c;vue成神之路★ ★ 解决算法&#xff0c;一个专栏就够了★ ★ 架…...

嵌入式一开始该怎么学?学习单片机

学习单片机&#xff1a; 模电数电肯定必须的&#xff0c;玩单片机大概率这两门课都学过&#xff0c;学过微机原理更好。 直接看野火的文档&#xff0c;芯片手册&#xff0c;外设手册。 学单片机不要纠结于某个型号&#xff0c;我认为stm32就OK&#xff0c;主要是原理和感觉。…...

Spring事件监听器ApplicationListener

目录 介绍 spirng启动后启动某方法 介绍 ApplicationEvent以及Listener是Spring为我们提供的一个事件监听、订阅的实现&#xff0c;内部实现原理是观察者设计模式&#xff0c;设计初衷也是为了系统业务逻辑之间的解耦&#xff0c;提高可扩展性以及可维护性。事件发布者并不需…...

安全学习DAY10_HTTP数据包

HTTP数据包 文章目录 HTTP数据包小节导图Request请求数据包结构Request请求方法&#xff08;方式&#xff09;请求头&#xff08;Header&#xff09;Response响应数据包结构Response响应数据包状态码状态码作用&#xff1a;部分状态码详解判断网站文件是否存在的状态码&#xf…...

云原生落地实践的25个步骤

一、什么是云原生&#xff1f; 云原生从字面意思上来看可以分成云和原生两个部分。 云是和本地相对的&#xff0c;传统的应用必须跑在本地服务器上&#xff0c;现在流行的应用都跑在云端&#xff0c;云包含了IaaS,、PaaS和SaaS。 原生就是土生土长的意思&#xff0c;我们在开始…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...