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

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)当题目输入的head
None时,直接返回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-排序链表问题题目题解方法&#xff1a;自顶向下归并排序算法题目 给你链表的头结点 head &#xff0c;请将其按 升序 排列并返回 排序后的链表 。 示例 1&#xff1a; 示例 2&#xff1a; 示例 3&#xff1a; 提示&#xff1a; *链表中节点的数目在范围 [0, 5 * 104]…...

c++之二叉树【进阶版】

前言 在c语言阶段的数据结构系列中已经学习过二叉树&#xff0c;但是这篇文章是二叉树的进阶版&#xff0c;因为首先就会讲到一种树形结构“二叉搜索树”&#xff0c;学习二叉搜索树的目标是为了更好的理解map和set的特性。二叉搜索树的特性就是左子树键值小于根&#xff0c;右…...

【数据库】 SQLServer

SQL Server 安装 配置 修改SQL Server默认的数据库文件保存路径_ 认识 master &#xff1a;是SQL Server中最重要的系统数据 库&#xff0c;存储SQL Server中的元数据。 Model&#xff1a;模板数据库&#xff0c;在创建新的数据库时&#xff0c;SQL Server 将会复制此数据…...

Linux 4.19 内核中 spinlock 概览

Linux内核中 spinlock相关数据结构和代码实现涉及的文件还是挺多的&#xff0c;这篇博客尝试从文件的角度来梳理一下 spinlock的相关数据结构和代码实现&#xff0c;适合想大概了解 Linux内核中 spinlock从上层 API到底层实现间的调用路径和传参变化&#xff0c;尤其适合了解 s…...

TensorFlow 1.x学习(系列二 :1):基本概念TensorFlow的基本介绍,图,会话,会话中的run(),placeholder(),常见的报错

目录1.基本介绍2.图的结构3.会话&#xff0c;会话的run方法4.placeholder5.返回值异常写在前边的话&#xff1a;之前发布过一个关于TensorFlow1.x的转载系列&#xff0c;自己将基本的TensorFlow操作敲了一遍&#xff0c;但是仍然有很多地方理解的不够深入。所以重开一个系列&am…...

javaEE 初阶 — 关于 IPv4、IPv6 协议、NAT(网络地址转换)、动态分配 IP 地址 的介绍

文章目录1. IPv42. IPv63. NAT4. 动态分配 IP 地址1. IPv4 在互联网的世界中只有 0 和1 &#xff0c;所以每个人都有一个由 0 和 1 组成的地址来让别人找到你。 这段由 0 和 1 组成的地址叫 IP 地址&#xff0c;这是互联网的基础资源&#xff0c;可以简单的理解为互联网的土地。…...

《Qt 6 C++开发指南》简介

我们编写的新书《Qt 6 C开发指南》在2月份终于正式发行销售了&#xff0c;这本书是对2018年5月出版的《Qt 5.9 C开发指南》的重磅升级。以下是本书前言的部分内容&#xff0c;算是对《Qt 6 C开发指南》的一个简介。1&#xff0e;编写本书的目的《Qt 5.9C开发指南》是我写的第一…...

CleanMyMac是什么清理软件?及使用教程

你知道CleanMyMac是什么吗&#xff1f;它的字面意思为“清理我的Mac”&#xff0c;作为软件&#xff0c;那就是一款Mac清理工具&#xff0c;Mac OS X 系统下知名系统清理软件&#xff0c;是数以万计的Mac用户的选择。它可以流畅地与系统性能相结合&#xff0c;只需简单的步骤就…...

Linux小黑板(9):共享内存

"My poor lost soul"上章花了不少的篇幅讲了讲基于管道((匿名、命名))技术实现的进程间通信。进程为什么需要通信&#xff1f;目的是为了完成进程间的"协同",提高处理数据的能力、优化业务逻辑的实现等等&#xff0c;在linux中我们已经谈过了一个通信的大类…...

Detr源码解读(mmdetection)

Detr源码解读(mmdetection) 1、原理简要介绍 整体流程&#xff1a; 在给定一张输入图像后&#xff0c;1&#xff09;特征向量提取&#xff1a; 首先经过ResNet提取图像的最后一层特征图F。注意此处仅仅用了一层特征图&#xff0c;是因为后续计算复杂度原因&#xff0c;另外&am…...

一个.Net Core开发的,撑起月6亿PV开源监控解决方案

更多开源项目请查看&#xff1a;一个专注推荐.Net开源项目的榜单 项目发布后&#xff0c;对于我们程序员来说&#xff0c;项目还不是真正的结束&#xff0c;保证项目的稳定运行也是非常重要的&#xff0c;而对于服务器的监控&#xff0c;就是保证稳定运行的手段之一。对数据库、…...

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、因为想在腾讯云的服务器上创建自己的数据库&#xff0c;所以我在这里是通过使用Xshell 7来连接腾讯云的远程服务器&#xff1b; 2、Xshell 7与服务器连接好之后&#xff0c;就可以开始进行数据库的安装了&#xff08;如果服务器曾经安装过数据库&#xff0c;得将之前安装的…...

13.STM32超声波模块讲解与实战

目录 1.超声波模块讲解 2.超声波时序图 3.超声波测距步骤 4.项目实战 1.超声波模块讲解 超声波传感器模块上面通常有两个超声波元器件&#xff0c;一个用于发射&#xff0c;一个用于接收。电路板上有4个引脚&#xff1a;VCC GND Trig&#xff08;触发&#xff09;&#xff…...

逆向之Windows PE结构

写在前面 对于Windows PE文件结构&#xff0c;个人认为还是非常有必要掌握和了解的&#xff0c;不管是在做逆向分析、免杀、病毒分析&#xff0c;脱壳加壳都是有着非常重要的技能。但是PE文件的学习又是一个非常枯燥过程&#xff0c;希望本文可以帮你有一个了解。 PE文件结构…...

ACL是什么

目录 一、ACL是什么 二、ACL的使用&#xff1a;setacl与getacl 1&#xff09;针对特定使用者的方式&#xff1a; 1. 创建acl_test1后设置其权限 2. 读取acl_test1的权限 2&#xff09;针对特定群组的方式&#xff1a; 3&#xff09;针对有效权限 mask 的设置方式&#xf…...

操作系统核心知识点整理--内存篇

操作系统核心知识点整理--内存篇按段对内存进行管理内存分区内存分页为什么需要多级页表TLB解决了多级页表什么样的缺陷?TLB缓存命中率高的原理是什么?段页结合: 为什么需要虚拟内存&#xff1f;虚拟地址到物理地址的转换过程段页式管理下程序如何载入内存&#xff1f;页面置…...

从零开始学习iftop流量监控(找出服务器耗费流量最多的ip和端口)

一、iftop是什么iftop是类似于top的实时流量监控工具。作用&#xff1a;监控网卡的实时流量&#xff08;可以指定网段&#xff09;、反向解析IP、显示端口信息等官网&#xff1a;http://www.ex-parrot.com/~pdw/iftop/二、界面说明>代表发送数据&#xff0c;< 代表接收数…...

第一篇博客------自我介绍篇

目录&#x1f506;自我介绍&#x1f506;学习目标&#x1f506;如何学习单片机Part 1 基础理论知识学习Part 2 单片机实践Part 3 单片机硬件设计&#x1f506;希望进入的公司&#x1f506;结束语&#x1f506;自我介绍 Hello!!!我是一名即已经步入大二的计算机小白。 --------…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

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

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

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...