【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周内 收录检索ÿ…...
《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...
AI语音助手的Python实现
引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...
DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态
前言 在人工智能技术飞速发展的今天,深度学习与大模型技术已成为推动行业变革的核心驱动力,而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心,系统性地呈现了两部深度技术著作的精华:…...
Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...
