力扣143:重排链表

给定一个单链表 L 的头节点 head ,单链表 L 表示为:

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例 1:

输入:head = [1,2,3,4]
输出:[1,4,2,3]

示例 2:

输入:head = [1,2,3,4,5]
输出:[1,5,2,4,3]

思想:先求得链表的中间结点,然后按照中间结点分为两个链表。将第二个链表进行逆转,然后和第一个链表进行合并。

代码:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*///找中间结点struct ListNode *middleNode(struct ListNode* head){struct ListNode *fast=head;struct ListNode *slow=head;while(fast != NULL && fast->next !=NULL){fast=fast->next->next;slow=slow->next;}return slow;}//逆转后半部分struct ListNode *reverse(struct ListNode *head){struct ListNode *pre=NULL;struct ListNode *p=head;struct ListNode *r;while(p!=NULL){r=p->next;p->next=pre;pre=p;p=r;}return pre;}//合并两个链表void merge(struct ListNode*L1,struct ListNode*L2){struct ListNode *p1;struct ListNode *p2;while(L1 != NULL && L2 != NULL){p1=L1->next;p2=L2->next;L1->next=L2;L1=p1;L2->next=L1;L2=p2;}}
void reorderList(struct ListNode* head) {if(head==NULL){return;}struct ListNode *mid=middleNode(head);struct ListNode *L1=head;struct ListNode *L2=mid->next;mid->next=NULL;L2=reverse(L2);merge(L1,L2);
}

时间复杂度O(n);空间复杂度O(n)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/456604.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

qt creator 转 visual stdio 项目调试

因果 大家在使用qt creator调试程序时,会出现未知错误,比如下图,直接release运行就没有问题。由于调试复杂程序,使用qt creator都感觉不如vs,会报未知中断。 所以有了从qt creator转换到 visual stdio来调试的想法。…

【电子元件】光通量和色温 (欧司朗LED灯珠 KW3 CGLNM1.TG命名规则)

什么是光通量? 光通量(Luminous Flux)是衡量光源在单位时间内发出的可见光总量的物理量,表示的是光源产生的总光能量,其中只考虑人眼能感知的部分。它通常以流明(lumen,符号为 lm)为…

如何使用gitlab切换分支

第一步,在gitlab上新建一个远程分支。选择New branch即可新建一个,但是注意往往是在当前分支下新建的分支,所以新分支里会有当前分支的内容。 第二步,在本地当前分支在运行这三行命令,即可得到一个空的新分支。 git c…

springboot2.0x 和springboot 1.0 整合redis 使用自定义CacheManager 问题

问题描述: 在我们深入理解springboot2.0x的缓存机制的时候,发现在springboot1.0 和springboot2.0 中默认的序列化都是使用的jdk的 Serializer 实现这个接口,jdk自带的序列化方法,由此我们需要自己去创建自定义的RedisCacheManager…

《Python游戏编程入门》注-第2章2

《Python游戏编程入门》的“2.2.5 绘制线条”中提到了通过pygame库绘制线条的方法。 1 相关函数介绍 通过pygame.draw模块中的line()函数来绘制线条,该函数的格式如下所示。 line(surface, color, start_pos, end_pos, width1) -> Rect 其中,第一…

AUTOSAR CP 中 BswM 模块功能与使用介绍(2/2)

三、 AUTOSAR BswM 模块详解及 ARXML 示例 BswM 模块的主要功能 BswM(Basic Software Mode Manager)模块在 AUTOSAR 架构中扮演着模式管理的核心角色。它负责管理车辆的各种模式(如启动、运行、停车等),并根据不同的…

基于vue框架的的电子商务网站68pwt(程序+源码+数据库+调试部署+开发环境)系统界面在最后面。

系统程序文件列表 项目功能:用户,商品分类,商品信息 开题报告内容 基于Vue框架的电子商务网站开题报告 一、研究背景与意义 随着互联网技术的不断发展和普及,电子商务已成为现代商业活动的重要组成部分。电子商务网站作为线上交易的主要平台&#xf…

Apple Vision Pro市场表现分析:IDC最新数据揭示的真相

随着AR/VR技术逐渐成熟并被更多消费者接受,2024年第二季度(Q2)成为这一领域的一个重要转折点。根据国际数据公司(IDC)发布的最新报告,整个AR/VR市场在本季度经历了显著的增长。接下来,我们将深入探讨Apple Vision Pro在这股增长浪潮中的具体表现。 市场背景 2024年Q2,…

Excel:vba实现生成随机数

Sub 生成随机数字()Dim randomNumber As IntegerDim minValue As IntegerDim maxValue As Integer 设置随机数的范围(假入班级里面有43个学生,学号是从1→43)minValue 1maxValue 43 生成随机数(在1到43之间生成随机数)randomNumber Application.WorksheetFunctio…

混个1024勋章

一眨眼毕业工作已经一年了,偶然进了游戏公司成了一名初级游戏服务器开发。前两天总结的时候,本来以为自己这一年没学到多少东西,但是看看自己的博客其实也有在进步,虽然比不上博客里的众多大佬,但是回头看也算是自己的…

.net 根据html的input type=“week“控件的值获取星期一和星期日的日期

初始化 "week" 控件值: //MVC部分 public ActionResult WeeklyList() {int weekNo new GregorianCalendar().GetWeekOfYear(System.DateTime.Now, System.Globalization.CalendarWeekRule.FirstDay, DayOfWeek.Sunday);string DefaultWeek DateTime.No…

利用移动式三维扫描技术创建考古文物的彩色纹理网格【上海沪敖3D】

文章来源于蔡司工业质量解决方案,作者蔡司工业质量 在考古环境中,三维扫描技术应用广泛,如存档、保存、复制和分享(包括实体和虚拟形式)。 文中,通过真实的扫描案例,您将了解到三维光学解决方案…

JavaWeb 23.一文速通npm的配置和使用

目录 一、npm的介绍 二、npm的安装和配置 1.安装 : 2.配置依赖下载使用阿里镜像 3. 配置全局依赖下载后存储位置 4.升级npm版本 5.环境变量配置 三、npm常用命令 1.项目初始化 npm.init npm init -y 2.安装依赖文件 3. 升级依赖 4.卸载依赖 5.查看依赖 查看项目…

Android 原生开发与Harmony原生开发浅析

Android系统 基于Linux ,架构如下 底层 (Linux )> Native ( C层) > FrameWork层 (SystemService) > 系统应用 (闹钟/日历等) 从Android发版1.0开始到现在15,经历了大大小小的变革 从Android6.0以下是个分水岭,6.0之前权限都是直接卸载Manifest中配置 6.0开始 则分普…

Rust的move关键字在线程中的使用

为什么使用 move? 在 Rust 中,move 关键字主要用于闭包。当我们在一个线程中创建一个闭包并将其传递给另一个线程时,如果闭包中使用了某些变量,就需要决定这些变量的所有权归属。 不使用 move: 默认情况下&#xff0…

LabVIEW提高开发效率技巧----事件日志记录

在LabVIEW开发中,集成事件日志记录系统是提升程序调试效率和确保系统运行稳定的关键步骤。通过记录关键操作和异常事件,开发人员可以快速定位问题、优化程序性能,并确保系统的稳定性和可靠性。 1. 事件日志的作用 事件日志是指在程序运行过…

python-PyQt项目实战案例:制作一个视频播放器

文章目录 1. 关键问题描述2. 通过OpenCV读取视频/打开摄像头抓取视频3. 通过PyQt 中的 QTimer定时器实现视频播放4. PyQt 视频播放器实现代码参考文献 1. 关键问题描述 在前面的文章中已经分享了pyqt制作图像处理工具的文章,也知道pyqt通过使用label控件显示图像的…

MySQL 初阶——多版本控制 MVCC

一、版本链(undo 日志) a. 什么是版本链 版本链就是一条以事务为节点的单链表。其 next 指针指向前一个版本的事务。 b. 版本链的增删 当一个事务被完成时,这个事务就会被加入到版本链里去;当要回滚时,版本链就会删…

微前端架构新选择:micro-app 框架一文全解析

目录 前言技术方案沙箱withiframe 环境变量主应用生命周期子应用生命周期初始化更新卸载缓存 JS 沙箱样式隔离元素隔离路由系统⭐数据通信⭐资源系统预加载umd 模式其他功能调试工具 前言 https://micro-zoe.github.io/micro-app/ micro-app 是由京东前端团队推出的一款微前端…

400V交流智能剩余电流监测系统设计与应用

摘要:针对变电站400V交流系统频繁发生剩余电流保护器跳闸的问题,本研究设计了一套智能化的分布式剩余电流监测系统。该系统利用CT传感器采集400V系统各负载端的剩余电流数据,经过运算处理后,将信息传递给交流绝缘监测装置。随后&a…