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

链表|148. 排序链表

148. 排序链表

题目:给你链表的头结点 head ,请将其按升序排列并返回排序后的链表。
在这里插入图片描述

题目链接: 148. 排序链表
时间复杂度:快排 O(n^2) 超出时间限制

class Solution {public ListNode sortList(ListNode head) {if(head==null){return head;}ListNode dummy=new ListNode(Integer.MIN_VALUE,null);ListNode pointnew=dummy;ListNode pointold=head;while(pointold!=null){while(pointnew!=null&&pointnew.next!=null){if(pointold.val<=pointnew.next.val){ListNode next=pointnew.next;ListNode node=new ListNode(pointold.val);pointnew.next=node;node.next=next;pointnew=dummy;break;}else{pointnew=pointnew.next;}}if(pointnew.next==null){ListNode next=pointnew.next;ListNode node=new ListNode(pointold.val);pointnew.next=node;node.next=next;pointnew=dummy;}pointold=pointold.next;}return dummy.next;}
}

归并排序O(logn):

class Solution {public ListNode sortList(ListNode head) {if(head==null||head.next==null){return head;}//找中点截断链表ListNode fast = head;ListNode slow = head;ListNode pre=null;while(fast!=null&&fast.next!=null){pre=slow;slow=slow.next;fast=fast.next.next;}//递归截断链表pre.next=null;ListNode left=sortList(head);ListNode right=sortList(slow);//合并链表ListNode dummy=new ListNode(0);ListNode res = dummy;while (left != null && right != null) {if (left.val < right.val) {res.next = left;left = left.next;} else {res.next = right;right = right.next;}res=res.next;}res.next=left!=null?left:right;return dummy.next;}
}

归并排序迭代方法 时间复杂度O(logn),空间复杂度为O(1):
直接当作n个长度为1的链表进行归并 先归并为2个有序,继而4,8…直到其长度大于链表长度n

public ListNode sortList(ListNode head) {if (head == null || head.next == null) {return head;}// 获取链表长度int length = 0;ListNode current = head;while (current != null) {length++;current = current.next;}ListNode dummy = new ListNode(0);dummy.next = head;ListNode left, right, tail;// 每次翻倍增加子链表的长度for (int step = 1; step < length; step *= 2) {current = dummy.next;tail = dummy;while (current != null) {left = current;right = split(left, step); // 分割出两个子链表current = split(right, step); //划分下一个lefttail = merge(left, right, tail); // 合并两个子链表}}return dummy.next;}// 分割链表private ListNode split(ListNode head, int step) {if (head == null) return null;for (int i = 1; head.next != null && i < step; i++) {head = head.next;}ListNode right = head.next;head.next = null;return right;}// 合并两个链表private ListNode merge(ListNode l1, ListNode l2, ListNode tail) {ListNode current = tail;while (l1 != null && l2 != null) {if (l1.val < l2.val) {current.next = l1;l1 = l1.next;} else {current.next = l2;l2 = l2.next;}current = current.next;}current.next = (l1 != null) ? l1 : l2;while (current.next != null) {current = current.next;}return current;}

相关文章:

链表|148. 排序链表

148. 排序链表 题目&#xff1a;给你链表的头结点 head &#xff0c;请将其按升序排列并返回排序后的链表。 题目链接&#xff1a; 148. 排序链表 时间复杂度&#xff1a;快排 O(n^2) 超出时间限制 class Solution {public ListNode sortList(ListNode head) {if(headnull)…...

如何解决5G基站高能耗问题?

安科瑞 须静燕 截至2023年10月&#xff0c;我国5G基站总数达321.5万个&#xff0c;占全国通信基站总数的28.1%。然而&#xff0c;随着5G基站数量的快速增长&#xff0c;基站的能耗问题也逐渐日益凸显&#xff0c;基站的用电给运营商带来了巨大的电费开支压力&#xff0c;降低5…...

PyTorch实现逻辑回归

最终效果 先看下最终效果&#xff1a; 这里用一条直线把二维平面上不同的点分开。 生成随机数据 #创建训练数据 x torch.rand(10,1)*10 #shape(10,1) y 2*x (5 torch.randn(10,1))#构建线性回归参数 w torch.randn((1))#随机初始化w&#xff0c;要用到自动梯度求导 b …...

什么是FPGA原型验证?

EDA工具的使用主要分为设计、验证和制造三大类。验证工作贯穿整个芯片设计流程&#xff0c;可以说芯片的验证阶段占据了整个芯片开发的大部分时间。从芯片需求定义、功能设计开发到物理实现制造&#xff0c;每个环节都需要进行大量的验证。 现如今验证方法也越来越多&#xff…...

基于VUE3+Layui从头搭建通用后台管理系统(前端篇)十四:系统设置模块相关功能实现

一、本章内容 本章使用已实现的公共组件实现系统管理中的系统设置模块相关功能,包括菜单管理、角色管理、日志管理、用户管理、系统配置、数据字典等。 1. 详细课程地址: 待发布 2. 源码下载地址: 待发布 二、界面预览 三、开发视频 3.1 B站视频地址:...

使用Visual Studio(VS)创建空项目的Win32桌面应用程序【main函数入口变WinMain】

前言 在Visual Studio中直接新建Windows桌面应用程序会有很多多余的代码生成&#xff0c;本文将提供从空项目创建Win32项目的方法&#xff0c;解决新建空项目直接使用WinMain代码编译报错的问题 例如&#xff1a;LNK2019 &#xff1a;无法解析的外部符号 参考博客&#xff1…...

基于自动化脚本批量上传依赖到nexus内网私服

前言 因为某些原因某些企业希望私服是不能连接外网的&#xff0c;所以需要某些开源依赖需要我们手动导入到nexus中&#xff0c;尽管nexus为我们提供了web页面。但是一个个手动导入显然是一个庞大的工程。 对此我们就不妨基于脚本的方式实现这一过程。 预期效果 笔者本地仓库…...

Linux中ps命令使用指南

目录 1 前言2 ps命令的含义和作用3 ps命令的基本使用4 常用选项参数5 一些常用情景5.1 查看系统中的所有进程&#xff08;标准语法&#xff09;5.2 使用 BSD 语法查看系统中的所有进程5.3 打印进程树5.4 获取线程信息5.5 获取安全信息5.6 查看以 root 用户身份&#xff08;实际…...

PHP开发语言中,网页端常用的标签

在PHP开发语言中&#xff0c;网页端常用的标签包括以下几种&#xff1a; <html>&#xff1a;用于定义整个HTML文档。<head>&#xff1a;用于定义文档的头部&#xff0c;包含元数据、样式表和脚本等。<title>&#xff1a;用于定义文档的标题&#xff0c;显示…...

Java 入门第四篇 集合

Java 入门第四篇 集合 一&#xff0c;什么是集合 在Java中&#xff0c;集合&#xff08;Collection&#xff09;是一种用于存储和操作一组对象的容器类。它提供了一系列的方法和功能&#xff0c;用于方便地管理和操作对象的集合。集合框架是Java中非常重要和常用的一部分&…...

VBA技术资料MF93:将多个Excel表插入PowerPoint不同位置

我给VBA的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的工作效率&#xff0c;而且可以提高数据的准确度。我的教程一共九套&#xff0c;分为初级、中级、高级三大部分。是对VBA的系统讲解&#xff0c;从简单的入门&#xff0c;到…...

STM32 MCU的易坑点收集

IIC配置中的Clock No Stretch Mode Clock Stretch Mode时钟延长模式&#xff1a; 时钟延长是一个术语&#xff0c;某些从设备可以把时钟线拉低&#xff0c;主设备发现自己释放时钟线之后时钟线还没有变成高电平&#xff0c;就会停止发送数据&#xff0c;然后等待从设备释放时钟…...

Vue3项目filter.js组件封装

1、element-plus(el-table)修改table的行样式 export function elTableRowClassName({ row, rowIndex }) {if (rowIndex % 2 ! 0) {return default-row} }2、时间戳转换格式 export function parseTimeFilter(dateTime, dateType) {if (dateTime || dateTime undefined ||…...

Linux: pwd命令查看当前工作目录

pwd 是 Linux 和其他类 Unix 操作系统中的一个命令&#xff0c;用于显示当前工作目录的绝对路径。 语法 pwd 描述 pwd 是 "print working directory" 的缩写&#xff0c;它用于打印当前工作目录的完整路径。这对于确定当前目录位置非常有用&#xff0c;特别是在嵌…...

【深度学习】PHP操作mysql数据库总结

一.PHP数据库的扩展分类 1.MySQL 扩展是针对 MySQL 4.1.3 或更早版本设计的&#xff0c;是 PHP 与 MySQL数据库交互的早期扩展。由于其不支持 MySQL 数据库服务器的新特性&#xff0c;且安全性差&#xff0c;在项目开发中不建议使用&#xff0c;可用 MySQLi 扩展代替。 2.MySQ…...

【送书活动】探究AIGC、AGI、GPT和人工智能大模型

文章目录 前言01 《ChatGPT 驱动软件开发》推荐语 02 《ChatGPT原理与实战》推荐语 03 《神经网络与深度学习》推荐语 04 《AIGC重塑教育》推荐语 05 《通用人工智能》推荐语 后记赠书活动 前言 人工智能技术在过去几年中发展迅猛&#xff0c;得益于大数据、云计算、深度学习等…...

Apple Find My「查找」认证芯片找哪家,认准伦茨科技ST17H6x芯片

深圳市伦茨科技有限公司&#xff08;以下简称“伦茨科技”&#xff09;发布ST17H6x Soc平台。成为继Nordic之后全球第二家取得Apple Find My「查找」认证的芯片厂家&#xff0c;该平台提供可通过Apple Find My认证的Apple查找&#xff08;Find My&#xff09;功能集成解决方案。…...

java.lang.IllegalArgumentException: Could not resolve placeholder XXX‘ in value

问题描述 使用Springcloudalibaba的nacos作为配置中心&#xff0c;服务启动时报错&#xff1a; java.lang.IllegalArgumentException: Could not resolve placeholder XXX‘ in value java.lang.IllegalArgumentException: Param ‘serviceName’ is illegal, serviceName is …...

自动机器学习是什么?概念及应用

自动机器学习 (Auto Machine Learning) 的应用和方法 随着众多企业在大量场景中开始采用机器学习&#xff0c;前后期处理和优化的数据量及规模指数级增长。企业很难雇用充足的人手来完成与高级机器学习模型相关的所有工作&#xff0c;因此机器学习自动化工具是未来人工智能 (A…...

el-date-picker限制选择7天内禁止内框选择

需求&#xff1a;elementPlus时间段选择框需要满足&#xff1a;①最多选7天时间。②不能手动输入。 <el-date-picker v-model"timeArrange" focus"timeEditable" :editable"false" type"datetimerange" range-separator"至&qu…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...