【LeetCode】148. 排序链表
排序链表
题目描述:
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
示例 1:
输入:head = [4,2,1,3] 输出:[1,2,3,4]
示例 2:
输入:head = [-1,5,3,4,0] 输出:[-1,0,3,4,5]
示例 3:
输入:head = [] 输出:[]
提示:
- 链表中节点的数目在范围
[0, 5 * 104]内 -105 <= Node.val <= 105
进阶:你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?
思路分析:
使用归并排序
大体实现:
-
基本情况处理:首先检查链表是否为空或只有一个节点。如果是,那么它已经是有序的,直接返回该链表。
-
分割链表:使用快慢指针技术找到链表的中点,并将链表从中点处分割成两个子链表。快指针
fast每次移动两步,慢指针slow每次移动一步,同时用一个prevPtr指针来记录slow的前一个节点,以便在找到中点后将链表分割。 -
递归排序:对分割后的两个子链表递归地调用
sortList方法进行排序。由于递归的性质,这两个子链表最终都会被分割成更小的子链表,直到每个子链表只包含一个节点(或为空),然后这些子链表会被合并成有序链表。 -
合并链表:使用
merge方法将两个已排序的子链表合并成一个有序链表。合并过程中,通过比较两个链表头节点的值,将较小的节点连接到结果链表的末尾,并移动相应的指针。当其中一个链表遍历完时,将另一个链表的剩余部分直接连接到结果链表的末尾。
细节解释
-
快慢指针:快指针
fast每次移动两步,慢指针slow每次移动一步。当快指针到达链表末尾时,慢指针正好位于链表的中点(或中点的前一个节点,如果链表长度为奇数)。prevPtr用于记录slow的前一个节点,以便在找到中点后将链表分割。 -
链表分割:通过将
prevPtr.next设置为null,可以将链表从中点处分割成两个子链表。prevPtr是slow的前一个节点,因此prevPtr.next = null会将slow及其后面的节点与前面的节点断开连接。(在使用快慢指针找到中点并分割链表时,需要确保链表长度至少为2,否则fast.next.next可能会引发NullPointerException。但在这个实现中,由于首先检查了链表是否为空或只有一个节点,所以这种情况不会发生。) -
递归调用:对分割后的两个子链表(
head和slow)public class Solution { // 主函数,用于对链表进行排序 public ListNode sortList(ListNode head) { // 如果链表为空或只有一个节点,则它已经是有序的,直接返回 if (head == null || head.next == null) { return head; } // 使用快慢指针找到链表的中点 ListNode slow = head; // 慢指针,每次移动一步 ListNode fast = head; // 快指针,每次移动两步 ListNode prevPtr = null; // 用于记录slow的前一个节点,以便分割链表 while (fast != null && fast.next != null) { prevPtr = slow; slow = slow.next; fast = fast.next.next; } // 分割链表:将链表从中间断开,prevPtr.next原本指向slow,现在设置为null prevPtr.next = null; // 递归地对左右两部分进行排序 // 注意:这里的left是原链表的左半部分,而right是原链表的右半部分(从slow开始) ListNode left = sortList(head); // 对左半部分排序 ListNode right = sortList(slow); // 对右半部分排序 // 合并两个有序链表 // 返回合并后的链表头节点 return merge(left, right); } // 合并两个有序链表的辅助函数 private ListNode merge(ListNode l1, ListNode l2) { // 创建一个哑节点,方便处理链表头部 ListNode dummy = new ListNode(0); ListNode tail = dummy; // tail用于遍历并连接合并后的链表 // 遍历两个链表,按序连接节点 while (l1 != null && l2 != null) { if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; } else { tail.next = l2; l2 = l2.next; } tail = tail.next; // 移动tail到当前连接的节点 } // 如果l1或l2还有剩余节点,直接将剩余部分连接到tail后面 if (l1 != null) { tail.next = l1; } if (l2 != null) { tail.next = l2; } // 返回合并后的链表(跳过哑节点) return dummy.next; } }分别递归调用
sortList方法进行排序。注意,这里的head是原链表的头节点,而slow是分割后右子链表的头节点。 -
合并链表:使用
merge方法将两个已排序的子链表合并成一个有序链表。合并过程中,通过比较两个链表头节点的值,将较小的节点连接到结果链表的末尾,并移动相应的指针。当其中一个链表遍历完时,另一个链表的剩余部分(如果有的话)将直接连接到结果链表的末尾。
代码实现:
public class Solution { // 主函数,用于对链表进行排序 public ListNode sortList(ListNode head) { // 如果链表为空或只有一个节点,则它已经是有序的,直接返回 if (head == null || head.next == null) { return head; } // 使用快慢指针找到链表的中点 ListNode slow = head; // 慢指针,每次移动一步 ListNode fast = head; // 快指针,每次移动两步 ListNode prevPtr = null; // 用于记录slow的前一个节点,以便分割链表 while (fast != null && fast.next != null) { prevPtr = slow; slow = slow.next; fast = fast.next.next; } // 分割链表:将链表从中间断开,prevPtr.next原本指向slow,现在设置为null prevPtr.next = null; // 递归地对左右两部分进行排序 // 注意:这里的left是原链表的左半部分,而right是原链表的右半部分(从slow开始) ListNode left = sortList(head); // 对左半部分排序 ListNode right = sortList(slow); // 对右半部分排序 // 合并两个有序链表 // 返回合并后的链表头节点 return merge(left, right); } // 合并两个有序链表的辅助函数 private ListNode merge(ListNode l1, ListNode l2) { // 创建一个哑节点,方便处理链表头部 ListNode dummy = new ListNode(0); ListNode tail = dummy; // tail用于遍历并连接合并后的链表 // 遍历两个链表,按序连接节点 while (l1 != null && l2 != null) { if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; } else { tail.next = l2; l2 = l2.next; } tail = tail.next; // 移动tail到当前连接的节点 } // 如果l1或l2还有剩余节点,直接将剩余部分连接到tail后面 if (l1 != null) { tail.next = l1; } if (l2 != null) { tail.next = l2; } // 返回合并后的链表(跳过哑节点) return dummy.next; }
}相关文章:
【LeetCode】148. 排序链表
排序链表 题目描述: 给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。 示例 1: 输入:head [4,2,1,3] 输出:[1,2,3,4]示例 2: 输入:head [-1,5,3,4,0] 输出:…...
阿里云-java调用短信服务,第三方接口的开启(傻瓜式教程)
第一步:在浏览器中,搜索阿里云 第二步:打开aly的主页 第三步:在最上方的导航栏中,找到云市场,注意不要点击,会自动有触发悬浮框出现,在悬浮框中找到 短信 第四步:点击 短…...
以node / link文件表征的道路网络-----基于南京公路公开数据做路径规划(下)------dijkstra算法的一些简单花样
在不改变dijkstra算法本身的情况下,完全可以从数据源的角度出发,解决我们的一些简单需求: 比较初级且粗暴的玩法,可以是强行赋予一些link极端的路段长度。 对于我们坚决不希望车辆行驶的道路、禁行区、或是危险区,就…...
计算机操作员中级理论知识试题
计算机操作员中级理论知识试题 一、单项选择题 在ASCII编码中,无法显示或打印的字符是()。 A.字符$,%,# B.运算符号*,.,/ C.空格 D.ASCII编码值在0-30间的控制符号将十进制数31.625转换成十六进制数是() A.115.10 B.If.a C.37.5 D.If.10在计算机中,同统一指挥和控制计…...
Redis主从同步配置
1: 安装Redis 参考 linux ubuntu安装redis_ubuntu离线安装redis7.2.5-CSDN博客 2:创建目录 到达redis 根目录 cd /usr/redis/# 创建主从工作目录 mkdir -p replication/6379 # master 节点 mkdir -p replication/6378 # 从节点 mkdir -p replication/6377 # 从节点…...
输出重定向
输出重定向是指将程序的输出(标准输出、错误输出等)重定向到指定的位置,而不是默认的输出设备(通常是终端/控制台)。在 Unix/Linux 系统中,输出重定向通过使用符号 >、>>、2> 等来实现。 常见…...
ubuntu20.04挂载机械硬盘
环境说明 1.基于清华源地址下载的ubuntu20.04制作的系统盘,然后安装在PC上(固态硬盘) 2.机械硬盘无法看见 目的 挂载机械硬盘,开机就能自动启动/挂载 参考链接 https://blog.csdn.net/qq_35624642/article/details/137713143…...
Python轻量级 NoSQL 数据库之tinydb使用详解
概要 在现代应用开发中,使用数据库来存储和管理数据是非常常见的需求。对于简单的数据存储需求,关系型数据库可能显得过于复杂。TinyDB 是一个纯 Python 实现的轻量级 NoSQL 数据库,专为嵌入式场景设计,适用于小型项目、原型开发和教学等场景。本文将详细介绍 TinyDB 库,…...
【数据结构】二叉树(二)遍历
上篇已经了解对二叉树有了大概了解,本篇学习二叉树的前序、中序、后序及层序遍历的递归与非递归共7种遍历方法,快收藏吧~ 目录 1、前序遍历 递归方式: 迭代方式: 2、中序遍历 递归方式: 迭代方式: …...
NGINX 常用内置变量
目录 $remote_addr 变量 $args 变量 $is_args 变量 $document_root 变量 $document_uri 变量 $host 变量 $limit_rate 变量 $remote_port 变量 $remote_port --显示客户端端口 $request_method 变量 --返回请求方式 $request_filename 变量 --返回请求实际路径 $request_uri…...
Windows采用VS2019实现Open3D的C++应用
1、参考链接 https://blog.csdn.net/qq_31254435/article/details/137799739 但是,我的方法和上述链接不大一样,我是采用VS2019进行编译的,方便在Windows平台上验证各种算法。 2、创建一个VS2019的C Console工程 #include <iostream>…...
冒泡排序、选择排序、插入排序,三种简单排序算法的区别?
1、冒泡排序 冒泡排序是从下标 1 遍历到 n,每当遇到大于下一个的,就和上一个交换位置,这样最大的就移动到了 n 的位置,然后从头再从 1 遍历到 n-1,把第二大的移动到 n-1 的位置,依此类推,每次从…...
Docker 日志管理
一、ELK -Filebeat Elasticsearch 数据的存储和检索 常用端口: 9100:elasticsearch-head提供web访问 9200:elasticsearch与其他程序连接或发送消息 9300:elasticsearch集群状态 Logstash 有三个组件构成input,fi…...
JavaScript初级——基础知识
一、JS的HelloWord 1、JS的代码需要编写到script标签中 2、JS的执行是根据语句从上到下一次执行的。 二、JS的编写位置 1、可以将js代码编写到标签的onclick属性中,当我们点击按钮时,js代码才会执行。 2、可以将js代码写在超链接的href属性中࿰…...
0817(持久层框架:JDBC,MyBatis)
三层架构(表现层,业务层,持久层) java中框架的概述(表现层、业务层、持久层的关系)_控制层业务层持久层的关系-CSDN博客 框架:框架一般处在低层应用平台(如J2EE)和高层…...
在亚马逊云科技上安全、合规地创建AI大模型训练基础设施并开发AI应用服务
项目简介: 小李哥将继续每天介绍一个基于亚马逊云科技AWS云计算平台的全球前沿AI技术解决方案,帮助大家快速了解国际上最热门的云计算平台亚马逊云科技AWS AI最佳实践,并应用到自己的日常工作里。 本次介绍的是如何在亚马逊云科技利用Servi…...
无人机模拟训练室技术详解
无人机模拟训练室作为现代无人机技术培训的重要组成部分,集成了高精度模拟技术、先进的数据处理能力及高度交互的操作界面,为无人机操作员提供了一个安全、高效、接近实战的训练环境。以下是对无人机模拟训练室技术的详细解析,涵盖系统基础概…...
【Spring框架】
一、引言二、Spring核心概念三、Spring入门示例四、进一步了解Spring的依赖注入五、Spring的面向切面编程(AOP)六、总结 一、引言 Spring框架自2003年发布以来,凭借其轻量级、易于扩展的特性,在Java企业级应用开发领域得到了广泛…...
uniapp 日常业务 随便写写 源码
现成的组件 直接用 <template><view style"margin: 10rpx;"><view class"tea-header"><text class"tea-title">礼尚往来</text><view class"tea-view-all"><text>查看全部</text>&l…...
【软件测试】单元测试20套练习题
(一)概述 使用Java语言编写应用程序,设计测试数据,完成指定要求的白盒测试,对测试数据及相应测试结果进行界面截图,将代码以及相关截图粘贴到白盒测试报告中。 (二)题目要求...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...
