Java-排序链表问题
Java-排序链表问题
- 题目
- 题解
- 方法:自顶向下归并排序
- 算法
题目
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
示例 1:

示例 2:

示例 3:

提示:
*链表中节点的数目在范围 [0, 5 * 104] 内
*-105 <= Node.val <= 105
进阶:你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?
题解
方法:自顶向下归并排序
对链表自顶向下归并排序的过程如下。
*找到链表的中点,以中点为分界,将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法,快指针每次移动 2 步,慢指针每次移动 1 步,当快指针到达链表末尾时,慢指针指向的链表节点即为链表的中点。*对两个子链表分别排序。*将两个排序后的子链表合并,得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法,将两个有序的子链表进行合并。*上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 1,即当链表为空或者链表只包含 1 个节点时,不需要对链表进行拆分和排序。

通过递归实现链表归并排序,有以下两个环节:
1.分割cut环节:找到当前链表中点,并从中点将链表断开(以便在下次递归cut时,链表片段拥有正确的边界);
(1)我们使用fast,slow快慢双指针法,奇数个结点找到中点,偶数个结点找到中心左边的结点。
(2)找到结点slow后,执行slow.next=None将链表切断。
(3)递归分割时,输入当前链表左端点head和中心结点slow的下一个结点tmp(因为链表是从slow切断的)。
(4)cut 递归终止条件:当head.nextNone时,说明只有一个结点,直接返回此结点。
2.合并merge环节:将两个排序链表合并,转化为一个排序链表。
(1)双指针法合并,建立辅助ListNode h作为头部。
(2)设置两指针left,right分别指向两链表头部,比较两指针处节点值的大小,由小到大加入合并链表头部,指针交替前进,直至添加完两个链表。
(3)返回辅助listNode h作为头部的下个结点h.next.
(4)时间复杂度O(1+r),l,r分别代表两个链表长度。
(5)当题目输入的headNone时,直接返回None.
算法
*///归并排序链表:1.从中间节点处拆分链表 2.通过双指针合并链表
class Solution {public ListNode sortList(ListNode head) {return sortList(head, null);}public ListNode sortList(ListNode head, ListNode tail) {if (head == null) {return head;}if (head.next == tail) { //sortList区间:[head,tail),说明此时区间中只有head一个元素head.next = null;return head;}//找到当前区间的中间节点ListNode slow = head, fast = head;while (fast != tail) {slow = slow.next;fast = fast.next;if (fast != tail) {fast = fast.next;}}ListNode mid = slow;//递归的拆分、合并链表ListNode list1 = sortList(head, mid);//sortList区间:[head,tail)ListNode list2 = sortList(mid, tail);ListNode sorted = merge(list1, list2);return sorted;}//类似于双指针法合并链表public ListNode merge(ListNode head1, ListNode head2) {ListNode dummyHead = new ListNode(0);ListNode temp = dummyHead, temp1 = head1, temp2 = head2;while (temp1 != null && temp2 != null) {if (temp1.val <= temp2.val) {temp.next = temp1;temp1 = temp1.next;} else {temp.next = temp2;temp2 = temp2.next;}temp = temp.next;}if (temp1 != null) {temp.next = temp1;} else if (temp2 != null) {temp.next = temp2;}return dummyHead.next;}
}
}相关文章:
Java-排序链表问题
Java-排序链表问题题目题解方法:自顶向下归并排序算法题目 给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。 示例 1: 示例 2: 示例 3: 提示: *链表中节点的数目在范围 [0, 5 * 104]…...
c++之二叉树【进阶版】
前言 在c语言阶段的数据结构系列中已经学习过二叉树,但是这篇文章是二叉树的进阶版,因为首先就会讲到一种树形结构“二叉搜索树”,学习二叉搜索树的目标是为了更好的理解map和set的特性。二叉搜索树的特性就是左子树键值小于根,右…...
【数据库】 SQLServer
SQL Server 安装 配置 修改SQL Server默认的数据库文件保存路径_ 认识 master :是SQL Server中最重要的系统数据 库,存储SQL Server中的元数据。 Model:模板数据库,在创建新的数据库时,SQL Server 将会复制此数据…...
Linux 4.19 内核中 spinlock 概览
Linux内核中 spinlock相关数据结构和代码实现涉及的文件还是挺多的,这篇博客尝试从文件的角度来梳理一下 spinlock的相关数据结构和代码实现,适合想大概了解 Linux内核中 spinlock从上层 API到底层实现间的调用路径和传参变化,尤其适合了解 s…...
TensorFlow 1.x学习(系列二 :1):基本概念TensorFlow的基本介绍,图,会话,会话中的run(),placeholder(),常见的报错
目录1.基本介绍2.图的结构3.会话,会话的run方法4.placeholder5.返回值异常写在前边的话:之前发布过一个关于TensorFlow1.x的转载系列,自己将基本的TensorFlow操作敲了一遍,但是仍然有很多地方理解的不够深入。所以重开一个系列&am…...
javaEE 初阶 — 关于 IPv4、IPv6 协议、NAT(网络地址转换)、动态分配 IP 地址 的介绍
文章目录1. IPv42. IPv63. NAT4. 动态分配 IP 地址1. IPv4 在互联网的世界中只有 0 和1 ,所以每个人都有一个由 0 和 1 组成的地址来让别人找到你。 这段由 0 和 1 组成的地址叫 IP 地址,这是互联网的基础资源,可以简单的理解为互联网的土地。…...
《Qt 6 C++开发指南》简介
我们编写的新书《Qt 6 C开发指南》在2月份终于正式发行销售了,这本书是对2018年5月出版的《Qt 5.9 C开发指南》的重磅升级。以下是本书前言的部分内容,算是对《Qt 6 C开发指南》的一个简介。1.编写本书的目的《Qt 5.9C开发指南》是我写的第一…...
CleanMyMac是什么清理软件?及使用教程
你知道CleanMyMac是什么吗?它的字面意思为“清理我的Mac”,作为软件,那就是一款Mac清理工具,Mac OS X 系统下知名系统清理软件,是数以万计的Mac用户的选择。它可以流畅地与系统性能相结合,只需简单的步骤就…...
Linux小黑板(9):共享内存
"My poor lost soul"上章花了不少的篇幅讲了讲基于管道((匿名、命名))技术实现的进程间通信。进程为什么需要通信?目的是为了完成进程间的"协同",提高处理数据的能力、优化业务逻辑的实现等等,在linux中我们已经谈过了一个通信的大类…...
Detr源码解读(mmdetection)
Detr源码解读(mmdetection) 1、原理简要介绍 整体流程: 在给定一张输入图像后,1)特征向量提取: 首先经过ResNet提取图像的最后一层特征图F。注意此处仅仅用了一层特征图,是因为后续计算复杂度原因,另外&am…...
一个.Net Core开发的,撑起月6亿PV开源监控解决方案
更多开源项目请查看:一个专注推荐.Net开源项目的榜单 项目发布后,对于我们程序员来说,项目还不是真正的结束,保证项目的稳定运行也是非常重要的,而对于服务器的监控,就是保证稳定运行的手段之一。对数据库、…...
C语言数据结构初阶(2)----顺序表
目录 1. 顺序表的概念及结构 2. 动态顺序表的接口实现 2.1 SLInit(SL* ps) 的实现 2.2 SLDestory(SL* ps) 的实现 2.3 SLPrint(SL* ps) 的实现 2.4 SLCheckCapacity(SL* ps) 的实现 2.5 SLPushBack(SL* ps, SLDataType x) 的实现 2.6 SLPopBack(SL* ps) 的实现 2.7 SLP…...
K8S常用命令速查手册
K8S常用命令速查手册一. K8S日常维护常用命令1.1 查看kubectl版本1.2 启动kubelet1.3 master节点执行查看所有的work-node节点列表1.4 查看所有的pod1.5 检查kubelet运行状态排查问题1.6 诊断某pod故障1.7 诊断kubelet故障方式一1.8 诊断kubelet故障方式二二. 端口策略相关2.1 …...
Linux系统下命令行安装MySQL5.6+详细步骤
1、因为想在腾讯云的服务器上创建自己的数据库,所以我在这里是通过使用Xshell 7来连接腾讯云的远程服务器; 2、Xshell 7与服务器连接好之后,就可以开始进行数据库的安装了(如果服务器曾经安装过数据库,得将之前安装的…...
13.STM32超声波模块讲解与实战
目录 1.超声波模块讲解 2.超声波时序图 3.超声波测距步骤 4.项目实战 1.超声波模块讲解 超声波传感器模块上面通常有两个超声波元器件,一个用于发射,一个用于接收。电路板上有4个引脚:VCC GND Trig(触发)ÿ…...
逆向之Windows PE结构
写在前面 对于Windows PE文件结构,个人认为还是非常有必要掌握和了解的,不管是在做逆向分析、免杀、病毒分析,脱壳加壳都是有着非常重要的技能。但是PE文件的学习又是一个非常枯燥过程,希望本文可以帮你有一个了解。 PE文件结构…...
ACL是什么
目录 一、ACL是什么 二、ACL的使用:setacl与getacl 1)针对特定使用者的方式: 1. 创建acl_test1后设置其权限 2. 读取acl_test1的权限 2)针对特定群组的方式: 3)针对有效权限 mask 的设置方式…...
操作系统核心知识点整理--内存篇
操作系统核心知识点整理--内存篇按段对内存进行管理内存分区内存分页为什么需要多级页表TLB解决了多级页表什么样的缺陷?TLB缓存命中率高的原理是什么?段页结合: 为什么需要虚拟内存?虚拟地址到物理地址的转换过程段页式管理下程序如何载入内存?页面置…...
从零开始学习iftop流量监控(找出服务器耗费流量最多的ip和端口)
一、iftop是什么iftop是类似于top的实时流量监控工具。作用:监控网卡的实时流量(可以指定网段)、反向解析IP、显示端口信息等官网:http://www.ex-parrot.com/~pdw/iftop/二、界面说明>代表发送数据,< 代表接收数…...
第一篇博客------自我介绍篇
目录🔆自我介绍🔆学习目标🔆如何学习单片机Part 1 基础理论知识学习Part 2 单片机实践Part 3 单片机硬件设计🔆希望进入的公司🔆结束语🔆自我介绍 Hello!!!我是一名即已经步入大二的计算机小白。 --------…...
Pixel Couplet Gen实战案例:某AI开发者大会现场扫码生成像素春联纪念品
Pixel Couplet Gen实战案例:某AI开发者大会现场扫码生成像素春联纪念品 1. 项目背景与创意来源 1.1 传统与创新的碰撞 在2024年某AI开发者大会现场,我们推出了一款名为"Pixel Couplet Gen"的互动装置。这款产品将中国传统春节文化与现代AI技…...
【人生底稿 03】2012 末日传说与我踏入 IT 的起点
接上《人生底稿》系列,本篇记录一段真实的成长碎片,不严格按时间线更新,只为记下一个农村少年,一步步走向社会的真实轨迹。 在参加某科技公司 ITMS 培训之前,我先经历了一轮面试 —— 上机题 技术面,分数…...
MediaPipe人脸检测避坑指南:如何优化检测精度与性能(含模型选择建议)
MediaPipe人脸检测实战优化:从参数调优到模型部署的完整指南 人脸检测作为计算机视觉的基础任务,其性能直接影响后续的面部分析效果。MediaPipe提供的轻量级解决方案在移动端和边缘设备上表现出色,但实际应用中常遇到误检、漏检或性能瓶颈问题…...
Mbed OS platform_drivers:嵌入式HAL驱动核心解析
1. 项目概述platform_drivers是 Arm Mbed OS 生态中一组经过严格验证、面向硬件抽象层(HAL)的平台级设备驱动集合,其核心定位并非提供通用外设封装,而是为 Mbed OS 内核及中间件组件提供可移植、可测试、符合 RTOS 语义的底层硬件…...
告别模糊边界!用Monodepth2实战KITTI深度估计,详解自动掩码与最小重投影损失
告别模糊边界!用Monodepth2实战KITTI深度估计,详解自动掩码与最小重投影损失 深度估计是计算机视觉领域的一项基础任务,它试图从2D图像中恢复出3D场景的几何信息。在自动驾驶、机器人导航、增强现实等应用中,准确的深度感知至关重…...
Nordic Power Profiler Kit II 保姆级教程:从硬件连接到软件操作全流程
Nordic Power Profiler Kit II 实战指南:从开箱到精准功耗分析 第一次拿到Power Profiler Kit II(PPK2)时,我正为一个蓝牙低功耗项目的电池寿命问题头疼不已。这款由Nordic Semiconductor推出的专业功耗分析工具,凭借其…...
shjshxksxjxbf
一、OpenAI 1.OpenAI是什么简单来说,OpenAI 大模型 是由美国人工智能公司 OpenAI 开发的一系列大型语言模型(LLMs) 。你可以把它们想象成拥有巨大“知识储备”和“学习能力”的超级大脑,它们被训练用来理解和生成人类语言…...
2026年3月上海污水处理设备生产厂家推荐:十大口碑产品评测对比知名
步入2026年3月,随着环保政策持续收紧与工业智能化升级的双重驱动,企业对污水处理设备的需求已从单纯的“达标排放”转向“高效、智能、全生命周期成本最优”。根据中国环保产业协会发布的《2026年度水处理装备市场趋势报告》,超过68%的采购决…...
新手福音:无需github,在快马平台轻松入门第一个web应用
最近在学前端开发时,发现很多教程都推荐从GitHub克隆项目来练习,但GitHub经常访问不稳定,对新手特别不友好。好在发现了InsCode(快马)平台,不用折腾GitHub就能直接上手写代码,特别适合我这种刚入门的小白。今天就用它做…...
终极OpenCore EFI自动化配置指南:OpCore-Simplify让你15分钟完成专业级黑苹果配置
终极OpenCore EFI自动化配置指南:OpCore-Simplify让你15分钟完成专业级黑苹果配置 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify 还在为复…...
