【Leetcode——重排链表】
文章目录
- 一、重排链表
- 思路1.
- 思路2.
- 总结
一、重排链表

对于这道题,有两种思路:
思路1.
1.使用一个线性表,存储链表中的每个节点,然后按照题目的条件,来链接线性表的各个节点即可。

使用左下标和右下标来定位线性表中的节点。
1.先存储链表中的节点数据到线性表
void reorderList(struct ListNode* head)
{struct ListNode* tmp[100000];int tail = 0;struct ListNode*cur = head;1.把链表中的节点存储到线性表中while(cur){tmp[tail++] = cur;cur = cur->next;}int front = 0;//由于下标从0开始,故需要--tailtail--;while(front<tail){tmp[front++]->next = tmp[tail];tmp[tail--]->next = tmp[front];}//到这一步必须置空,否则出现自己的next指向自己,出现环状//并且需要是front的next置空,因为在循环中tail和front已经错过了。tmp[front]->next = NULL;return head;
}
2.循环条件是front < tail
时间复杂度为O(N),空间复杂度为O(N)
思路2.
(1)找到链表的中间节点
(2)将链表中间节点开始之后的链表逆置
(3)将两个链表重新合并
(1)找链表的中间节点可以使用快慢指针来求出。
快指针一次走两步,慢指针一次走一步。

(2)链表逆置,有两种方法,一种方法是使用三指针,一种方法是使用头插。
三指针法:

(3)合并两个链表,合并链表,从两个链表的头节点开始链接。

struct ListNode *middleNode(struct ListNode*head)
{struct ListNode*fast = head,*slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow;
}struct ListNode* reverseList(struct ListNode*head)
{struct ListNode*prev = NULL;struct ListNode*cur = head;while(cur){struct ListNode*next = cur->next;cur->next = prev;prev = cur;cur = next;}return prev;
}void mergeList(struct ListNode*head,struct ListNode*head2)
{struct ListNode*l2 = head2,*l1 = head;while(l1 && l2){struct ListNode*l1next = l1->next;struct ListNode*l2next = l2->next;l1->next = l2;l1 = l1next;l2->next = l1;l2 = l2next;}
}
void reorderList(struct ListNode* head)
{if (head == NULL || head->next == NULL){return;}//1.找中间节点struct ListNode *midnode = middleNode(head);//2.逆置中间节点之后的链表//3.按照题目合并链表struct ListNode*head2 = midnode->next;midnode->next = NULL;//把它置空,其实是把midnode纳入第一条链表中的最后一个节点了//对后半链表逆置head2 = reverseList(head2);mergeList(head,head2); }
时间复杂度O(n),空间复杂度O(1)
总结
两种方法各有好处,法1空间复杂度大,但是易于理解。
法2相对更难理解,但是空间复杂度小。
相关文章:
【Leetcode——重排链表】
文章目录一、重排链表思路1.思路2.总结一、重排链表 对于这道题,有两种思路: 思路1. 1.使用一个线性表,存储链表中的每个节点,然后按照题目的条件,来链接线性表的各个节点即可。 使用左下标和右下标来定位线性表中的…...
HCIP总结(一)
抽象语言---编码---二进制---电信号----处理电信号 (电脑工作流程) OSI参考模型 ----OSI/RM (核心思想:分层) 应用层----提供各种应用服务,将抽象语言转换成编码,提供人机交互的接口 表示层----将编码转换成二进制 …...
华为OD机试真题Python实现【黑板上色】真题+解题思路+代码(20222023)
题目 疫情过后希望小学终于又重新开学了,3 年 2 班开学第一天的任务是将后面的黑板报重新制作, 黑板上已经写上了N个正整数,同学们需要给这每个数分别上一种颜色, 为了让黑板报既美观又有学习意义,老师要求同种颜色的所有数都可以被这个颜色中最小的那个数整除, 现在帮小…...
C++中的利器——模板
前文本文主要是讲解一下C中的利器——模板,相信铁子们在学完这一节后,写代码会更加的得心应手,更加的顺畅。一,泛型编程想要学习模板,我们要先了解为什么需要模板,我们可以看看下面这个程序。int add(int&a…...
k8s控制器
目录 一、控制器简介 二、控制器类型 1、RC和RS 2、Deployment 3、DaemonSet 4、Job 5、CronJob 6、StateFulSet 7、HPA 一、控制器简介 在kubernetes中,按照Pod的创建方式可以将其分为两类: 自主式:kubernetes直接创建出来的Pod,…...
嵌入式学习笔记——认识STM32的 GPIO口
寄存器开发STM32GPIO口前言认识GPIOGPIO是什么GPIO有什么用GPIO怎么用STM32上GPIO的命名以及数量GPIO口的框图(重点)输入框图解析三种输入模式GPIO输入时内部器件及其作用1.保护二极管2.上下拉电阻(可配置)3.施密特触发器4.输入数…...
类和对象(中)
文章目录 继承的概念继承的语法父类成员访问super关键字子类构造方法super和this初始化protected关键字继承方式final关键字继承与组合一、继承的概念 继承(inheritance)机制:是面向对象程序设计使代码可以复用的最重要的手段,它允许程序员在保持原有类…...
Java——单词接龙
题目链接 leetcode在线oj题——单词接龙 题目描述 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk: 每一对相邻的单词只差一个字母。 对于 1 < i < k 时ÿ…...
HTML DOM 事件监听器
通过JavaScript,我们可以给页面的某些元素添加事件的监听器,当元素触发相应事件的时候监听器就会捕捉到这个事件并执行相应的代码。addEventListener() 方法实例当用户点击按钮时触发监听事件:document.getElementById("myBtn").ad…...
java基本数据类型取值范围
在JAVA中一共有八种基本数据类型,他们分别是 byte、short、int、long、float、double、char、boolean 整型 其中byte、short、int、long都是表示整数的,只不过他们的取值范围不一样 byte的取值范围为-128~127,占用1个字节(-2的…...
maven的安装配置
目录 1. Maven的安装配置 1.1检测jdk的版本 1.2下载maven 1.3配置maven环境变量 2.认识maven的目录结构 2.1 创建一个文件夹作为项目的根目录 1.创建如下结构的目录 2. 在pom.xml文件中写入如下内容(不用记忆) 3.在mian-->java--》下边创建java文件编辑 4.cmd下…...
【转载】System Verilog 上下文context的含义以及设置导入函数的作用域
放丢失,转载一下,原文:https://blog.csdn.net/qq_31348733/article/details/1010546251. 上下文(context)的含义导入函数的上下文是该函数定义所在的位置,比如$unit 、模块、program或者package作用域(scope),这一点跟…...
redis数据类型
Redis 数据类型 redis无论什么数据类型,在数据库中都是以key-value形式保存,并且所有的key(键)都是字符串,所以讨论基础数据结构都是讨论的value值的数据类型 1. 字符串操作 set key value [ex seconds] [px milliseconds] [nx|xx] 设置ke…...
【独家】华为OD机试 - 最多获得的短信条数(C 语言解题)
最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧文章目录 最近更新的博客使用说明本期…...
【剧前爆米花--爪哇岛寻宝】包装类的装拆箱和泛型的擦除机制
作者:困了电视剧 专栏:《数据结构--Java》 文章分布:这是关于数据结构的基础之一泛型的文章,希望对你有所帮助。 目录 包装类 装箱 装箱源码小细节 拆箱 泛型 什么是泛型 泛型编译的擦除机制 不能实例化泛型类型数组 包装…...
BufferQueue研究
我们在工作的过程中,肯定听过分析卡顿或者冻屏问题的时候,定位到APP卡在dequeueBuffer方法里面,或者也听身边的同事老说3Buffer等信息。所以3Buffer是什么鬼?什么是BufferQueue?搞Android,你一定知道Graphic Buffer和…...
【计组笔记08】计算机组成与原理之IO设备系统(输入、输出设备、外存储器)
这篇文章,主要介绍计算机组成与原理之IO设备系统(输入、输出设备、外存储器)。 目录 一、IO设备系统 1.1、IO系统的演变 (1)早期阶段 (2)接口模块和DMA阶段...
使用Vue实现数据可视化大屏功能(一)
导语 现在在很多的工程项目中,都有有关于数据大屏相关的监控内容,这里我们就来看一下如何用Vue来搭建一个数据可视化大屏应用。 创建项目 使用WebStorm工具创建一个Vue的项目。如下图所示,配置好vue的脚手架工具和nodejs的运行环境&#…...
华为OD机试真题Python实现【整数对最小和】真题+解题思路+代码(20222023)
整数对最小和 题目 给定两个整数数组 array1 array2 数组元素按升序排列 假设从array1 array2中分别取出一个元素可构成一对元素 现在需要取出K个元素 并对取出的所有元素求和 计算和的最小值 注意: 两对元素如果对应于array1 array2中的两个下标均相同,则视为同一个元素 �…...
2023年绿色建筑国际会议(ICoGB 2023)
2023年绿色建筑国际会议(ICoGB 2023) 重要信息 会议网址:www.icogb.org 会议时间:2023年5月19-21日 召开地点:斯德哥尔摩 截稿时间:2023年4月1日 录用通知:投稿后2周内 收录检索ÿ…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
