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

对链表进行排序最适合的算法就是归并排序:
对链表自顶向下归并排序的过程:
- 找到链表的中点,以中点为分界,将链表拆分成两个子链表,寻找链表的中点可以使用快慢指针的做法,快指针每次移动 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.排序链表 对链表进行排序最适合的算法就是归并排序: 对链表自顶向下归并排序的过程: 找到链表的中点,以中点为分界,将链表拆分成两个子链表,寻找链表的中点可以使用快慢指针的做法,快指针每次移动 2步…...
分布式并行训练(DP、DDP、DeepSpeed)
[pytorch distributed] 01 nn.DataParallel 数据并行初步 数据并行 vs. 模型并行 数据并行:模型拷贝(per device),数据 split/chunk(对batch切分) 每个device上都拷贝一份完整模型,每个device分…...
Linux- fg命令 bg命令
fg fg是Unix-like操作系统(如Linux和macOS)中的一个shell内建命令,用于将后台作业带到前台执行。这个命令常用于与bg(后台执行)命令和jobs(列出当前作业)命令一起,进行shell中的作业…...
leetcode第362场周赛
2873. 有序三元组中的最大值 I 核心思想:由于这题数据范围比较小,直接枚举i,j,k即可。 2874. 有序三元组中的最大值 II 核心思想:这题是在2873题目的基础上将数据范围进行了增加,意味着我们需要对上面的代码进行优化。两种优化方…...
图神经网络GNN(一)GraphEmbedding
DeepWalk 使用随机游走采样得到每个结点x的上下文信息,记作Context(x)。 SkipGram优化的目标函数:P(Context(x)|x;θ) θ argmax P(Context(x)|x;θ) DeepWalk这种GraphEmbedding方法是一种无监督方法,个人理解有点类似生成模型的Encoder过程…...
多目标平衡优化器黏菌算法(MOEOSMA)求解CEC2020多模式多目标优化
多目标平衡优化器黏菌算法(MOEOSMA)比现有的多目标黏菌算法具有更好的优化性能。在MOEOSMA中,动态系数用于调整勘探和开采趋势。采用精英存档机制来促进算法的收敛性。使用拥挤距离法来保持Pareto前沿的分布。采用平衡池策略模拟黏菌的协同觅…...
快速开发微信小程序之一登录认证
一、背景 记得11、12年的时候大家一窝蜂的开始做客户端Android、IOS开发,我是14年才开始做Andoird开发,干了两年多,然后18年左右微信小程序火了,我也做了两个小程序,一个是将原有牛奶公众号的功能迁移到小程序&#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,match_phrase,term, 参考:https://zhuanlan.zhihu.com/p/592767668?utm_id0 1、全量查询分页指定source 示例:请求地址为http://127.0.0.1:9200/students/_search,请求体为: {"query":…...
【VIM】初步认识VIM-2
2-6 Vim 如何搜索替换_哔哩哔哩_bilibili 1-6行将self改成this 精确替换quack单词为交...
《HelloGitHub》第 90 期
兴趣是最好的老师,HelloGitHub 让你对编程感兴趣! 简介 HelloGitHub 分享 GitHub 上有趣、入门级的开源项目。 https://github.com/521xueweihan/HelloGitHub 这里有实战项目、入门教程、黑科技、开源书籍、大厂开源项目等,涵盖多种编程语言 …...
Apache Hudi初探(五)(与flink的结合)--Flink 中hudi clean操作
背景 本文主要是具体说说Flink中的clean操作的实现 杂说闲谈 在flink中主要是CleanFunction函数: Overridepublic void open(Configuration parameters) throws Exception {super.open(parameters);this.writeClient FlinkWriteClients.createWriteClient(conf,…...
stream对list数据进行多字段去重
方法一: //根据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镜像演练环境,包含五个系列共23道漏洞分析和利用实战题目。 Protostar的安装有两种方式 第一种是下载镜像并安装虚拟机https://github.com/Exp…...
go基础语法10问
1.使用值为 nil 的 slice、map会发生啥 允许对值为 nil 的 slice 添加元素,但对值为 nil 的 map 添加元素,则会造成运行时 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基本操作
功能: 命令行模式下的文本编辑器。根据文件扩展名自动判别编程语言。支持代码缩进、代码高亮等功能。使用方式:vim filename 如果已有该文件,则打开它。 如果没有该文件,则打开个一个新的文件,并命名为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()算子,适用于一些无法用单一灰度进行分割的情况,如背景比较复杂,有的部分比前景目标亮,或者有的部分比前景目标暗;又比如前景目标包…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
Python Einops库:深度学习中的张量操作革命
Einops(爱因斯坦操作库)就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库,用类似自然语言的表达式替代了晦涩的API调用,彻底改变了深度学习工程…...
【 java 虚拟机知识 第一篇 】
目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...
