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

【LeetCode热题100】--148.排序链表

148.排序链表

image-20231002221349966

对链表进行排序最适合的算法就是归并排序:
对链表自顶向下归并排序的过程:

  • 找到链表的中点,以中点为分界,将链表拆分成两个子链表,寻找链表的中点可以使用快慢指针的做法,快指针每次移动 2步,慢指针每次移动 1步,当快指针到达链表末尾时,慢指针指向的链表节点即为链表的中点
  • 对两个子链表分别排序
  • 将两个排序后的子链表合并,得到完整的排序后的链表

上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 1,即当链表为空或者链表只包含 1个节点时,不需要对链表进行拆分和排序。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
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){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);ListNode list2= sortList(mid,tail);ListNode sorted = merge(list1,list2);return sorted;}public ListNode merge(ListNode head1,ListNode head2){  //合并两个有序链表ListNode dummy = new ListNode(0);ListNode temp = dummy,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 dummy.next;}
}

相关文章:

【LeetCode热题100】--148.排序链表

148.排序链表 对链表进行排序最适合的算法就是归并排序&#xff1a; 对链表自顶向下归并排序的过程&#xff1a; 找到链表的中点&#xff0c;以中点为分界&#xff0c;将链表拆分成两个子链表&#xff0c;寻找链表的中点可以使用快慢指针的做法&#xff0c;快指针每次移动 2步…...

分布式并行训练(DP、DDP、DeepSpeed)

[pytorch distributed] 01 nn.DataParallel 数据并行初步 数据并行 vs. 模型并行 数据并行&#xff1a;模型拷贝&#xff08;per device&#xff09;&#xff0c;数据 split/chunk&#xff08;对batch切分&#xff09; 每个device上都拷贝一份完整模型&#xff0c;每个device分…...

Linux- fg命令 bg命令

fg fg是Unix-like操作系统&#xff08;如Linux和macOS&#xff09;中的一个shell内建命令&#xff0c;用于将后台作业带到前台执行。这个命令常用于与bg&#xff08;后台执行&#xff09;命令和jobs&#xff08;列出当前作业&#xff09;命令一起&#xff0c;进行shell中的作业…...

leetcode第362场周赛

2873. 有序三元组中的最大值 I 核心思想&#xff1a;由于这题数据范围比较小&#xff0c;直接枚举i,j,k即可。 2874. 有序三元组中的最大值 II 核心思想&#xff1a;这题是在2873题目的基础上将数据范围进行了增加&#xff0c;意味着我们需要对上面的代码进行优化。两种优化方…...

图神经网络GNN(一)GraphEmbedding

DeepWalk 使用随机游走采样得到每个结点x的上下文信息&#xff0c;记作Context(x)。 SkipGram优化的目标函数&#xff1a;P(Context(x)|x;θ) θ argmax P(Context(x)|x;θ) DeepWalk这种GraphEmbedding方法是一种无监督方法&#xff0c;个人理解有点类似生成模型的Encoder过程…...

多目标平衡优化器黏菌算法(MOEOSMA)求解CEC2020多模式多目标优化

多目标平衡优化器黏菌算法&#xff08;MOEOSMA&#xff09;比现有的多目标黏菌算法具有更好的优化性能。在MOEOSMA中&#xff0c;动态系数用于调整勘探和开采趋势。采用精英存档机制来促进算法的收敛性。使用拥挤距离法来保持Pareto前沿的分布。采用平衡池策略模拟黏菌的协同觅…...

快速开发微信小程序之一登录认证

一、背景 记得11、12年的时候大家一窝蜂的开始做客户端Android、IOS开发&#xff0c;我是14年才开始做Andoird开发&#xff0c;干了两年多&#xff0c;然后18年左右微信小程序火了&#xff0c;我也做了两个小程序&#xff0c;一个是将原有牛奶公众号的功能迁移到小程序&#x…...

Mybatis配置文件(mybatis-config.xml)和Mapper映射文件(XXXMapper.xml)模板

配置文件 ${dirver} ---> com.mysql.jdbc.Driver ${url} ---> jdbc:mysql://localhost:3306/数据库名 <?xml version"1.0" encoding"UTF-8" ?> <!DOCTYPE configurationPUBLIC "-//mybatis.org//DTD Config 3.0//EN""h…...

4. 条件查询

首先区分下match&#xff0c;match_phrase,term, 参考&#xff1a;https://zhuanlan.zhihu.com/p/592767668?utm_id0 1、全量查询分页指定source 示例&#xff1a;请求地址为http://127.0.0.1:9200/students/_search&#xff0c;请求体为&#xff1a; {"query":…...

【VIM】初步认识VIM-2

2-6 Vim 如何搜索替换_哔哩哔哩_bilibili 1-6行将self改成this 精确替换quack单词为交...

《HelloGitHub》第 90 期

兴趣是最好的老师&#xff0c;HelloGitHub 让你对编程感兴趣&#xff01; 简介 HelloGitHub 分享 GitHub 上有趣、入门级的开源项目。 https://github.com/521xueweihan/HelloGitHub 这里有实战项目、入门教程、黑科技、开源书籍、大厂开源项目等&#xff0c;涵盖多种编程语言 …...

Apache Hudi初探(五)(与flink的结合)--Flink 中hudi clean操作

背景 本文主要是具体说说Flink中的clean操作的实现 杂说闲谈 在flink中主要是CleanFunction函数&#xff1a; Overridepublic void open(Configuration parameters) throws Exception {super.open(parameters);this.writeClient FlinkWriteClients.createWriteClient(conf,…...

stream对list数据进行多字段去重

方法一&#xff1a; //根据sj和name去重 List<NursingHandover> testList list.stream().collect(Collectors.collectingAndThen(Collectors.toCollection(() -> new TreeSet<>(Comparator.comparing(o -> o.getj() ";" o.getName() ";&…...

一种基于体素的射线检测

效果 基于体素的射线检测 一个漏检的射线检测 从起点一直递增指定步长即可得到一个稀疏的检测 bool Raycast(Vector3 from, Vector3 forword, float maxDistance){int loop 6666;Vector3 pos from;Debug.DrawLine(from, from forword * maxDistance, Color.red);while (loo…...

利用Docker安装Protostar

文章目录 一、Protostar介绍二、Ubuntu下安装docker三、安装Protostar 一、Protostar介绍 Protostar是一个免费的Linux镜像演练环境&#xff0c;包含五个系列共23道漏洞分析和利用实战题目。 Protostar的安装有两种方式 第一种是下载镜像并安装虚拟机https://github.com/Exp…...

go基础语法10问

1.使用值为 nil 的 slice、map会发生啥 允许对值为 nil 的 slice 添加元素&#xff0c;但对值为 nil 的 map 添加元素&#xff0c;则会造成运行时 panic。 // map 错误示例 func main() {var m map[string]intm["one"] 1 // error: panic: assignment to entry i…...

SpringCloud + SpringGateway 解决Get请求传参为特殊字符导致400无法通过网关转发的问题

title: “SpringCloud SpringGateway 解决Get请求传参为特殊字符导致400无法通过网关转发的问题” createTime: 2021-11-24T10:27:5708:00 updateTime: 2021-11-24T10:27:5708:00 draft: false author: “Atomicyo” tags: [“tomcat”] categories: [“java”] description: …...

vim基本操作

功能&#xff1a; 命令行模式下的文本编辑器。根据文件扩展名自动判别编程语言。支持代码缩进、代码高亮等功能。使用方式&#xff1a;vim filename 如果已有该文件&#xff0c;则打开它。 如果没有该文件&#xff0c;则打开个一个新的文件&#xff0c;并命名为filename 模式…...

Drift plus penalty 漂移加惩罚Part1——介绍和工作原理

文章目录 正文Methodology 方法论Origins and applications 起源和应用How it works 它是怎样工作的The stochastic optimization problem 随机优化问题Virtual queues 虚拟队列The drift-plus-penalty expression 漂移加惩罚表达式Drift-plus-penalty algorithmApproximate sc…...

(四)动态阈值分割

文章目录 一、基本概念二、实例解析 一、基本概念 基于局部阈值分割的dyn_threshold()算子&#xff0c;适用于一些无法用单一灰度进行分割的情况&#xff0c;如背景比较复杂&#xff0c;有的部分比前景目标亮&#xff0c;或者有的部分比前景目标暗&#xff1b;又比如前景目标包…...

YOLOv8工业缺陷检测推理延迟骤降63%:基于TensorRT量化+ONNX Runtime定制化内核的完整链路

第一章&#xff1a;YOLOv8工业缺陷检测推理延迟骤降63%&#xff1a;基于TensorRT量化ONNX Runtime定制化内核的完整链路在高吞吐产线场景下&#xff0c;YOLOv8原生PyTorch模型在Jetson AGX Orin上单帧推理延迟达84.2ms&#xff08;输入尺寸640640&#xff09;&#xff0c;严重制…...

luci-app-unblockneteasemusic 插件完整技术指南:实现网易云音乐播放限制解除

luci-app-unblockneteasemusic 插件完整技术指南&#xff1a;实现网易云音乐播放限制解除 【免费下载链接】luci-app-unblockneteasemusic [OpenWrt] 解除网易云音乐播放限制 项目地址: https://gitcode.com/gh_mirrors/lu/luci-app-unblockneteasemusic luci-app-unblo…...

Buildroot构建根文件系统时,为什么你的rootfs.tar总比别人的大?深度解析裁剪技巧

Buildroot构建根文件系统时rootfs.tar体积优化实战指南 当你在嵌入式Linux开发中使用Buildroot构建根文件系统时&#xff0c;是否经常遇到生成的rootfs.tar文件体积过大的问题&#xff1f;本文将深入解析Buildroot的打包机制&#xff0c;揭示那些容易被忽视的体积膨胀陷阱&…...

160+实用功能:OneMore插件如何让OneNote笔记管理效率翻倍?[特殊字符]

160实用功能&#xff1a;OneMore插件如何让OneNote笔记管理效率翻倍&#xff1f;&#x1f680; 【免费下载链接】OneMore A OneNote add-in with simple, yet powerful and useful features 项目地址: https://gitcode.com/gh_mirrors/on/OneMore 还在为OneNote单调的功…...

新手避坑指南:用MATLAB复现TI IWR1443雷达的距离与速度FFT处理(附完整代码)

新手避坑指南&#xff1a;用MATLAB复现TI IWR1443雷达的距离与速度FFT处理&#xff08;附完整代码&#xff09; 第一次拿到IWR1443毫米波雷达开发板时&#xff0c;看着官方文档里密密麻麻的英文术语和零散的代码片段&#xff0c;我对着电脑屏幕发呆了整整半小时。作为电子工程专…...

DeepSeek-OCR实战教程:批量处理脚本编写与异步解析任务队列设计

DeepSeek-OCR实战教程&#xff1a;批量处理脚本编写与异步解析任务队列设计 1. 学习目标与场景引入 如果你正在处理大量的文档图片&#xff0c;比如扫描的合同、发票、报告或者历史档案&#xff0c;一张张上传到DeepSeek-OCR界面手动处理&#xff0c;不仅效率低下&#xff0c…...

Simulink与Plecs联合仿真实现三相桥式电路能量双向流动

simulinkplecs联合仿真源件&#xff0c;三相桥式电路&#xff0c;采用母线电压外环与电流内环控制&#xff0c;可整流也可逆变并网&#xff0c;实现能量双向流动&#xff0c;采用SVPWM调制方式。 1.plecssimulink 2.SVPWM 3.双闭环 支持simulink2022以下版本&#xff0c;联系跟…...

4重防护构建安卓安全屏障:APKMirror应用管理全攻略

4重防护构建安卓安全屏障&#xff1a;APKMirror应用管理全攻略 【免费下载链接】APKMirror 项目地址: https://gitcode.com/gh_mirrors/ap/APKMirror 在安卓应用下载的数字丛林中&#xff0c;恶意软件如同潜伏的猎手&#xff0c;时刻准备利用用户对新版本的渴望发起攻击…...

I-Lang SEO实战部署:用结构化协议让Google的AI爬虫读懂你的网页

前言&#xff1a; 我们用I-Lang的结构化方法论做SEO&#xff0c;一个全新的英文商业站&#xff0c;七天打进Google搜索第一页。这篇文章把具体方法公开。 一、前提&#xff1a;Google的爬虫已经是AI了 2024年之后&#xff0c;Google的搜索排名算法发生了根本性变化。Googlebot…...

零基础手写大模型

从零搭建大模型&#xff1a;零基础学习实现职业经济跃迁指南 引言 在人工智能重塑全球产业格局的今天&#xff0c;“大模型”已不再仅仅是科技巨头的专利&#xff0c;而是成为了数字经济时代新的“电力”与“石油”。对于广大职场人士、创业者及寻求转型的个体而言&#xff0…...