排序链表(归并排序)
148. 排序链表 - 力扣(LeetCode)
以O(nlogn)时间复杂度, O(1)空间复杂度 排序链表
涉及知识点:
- 找到链表的中间节点 2095. 删除链表的中间节点 - 力扣(LeetCode)
- 合并有序链表 21. 合并两个有序链表 - 力扣(LeetCode)
- 归并排序 912. 排序数组 - 力扣(LeetCode)
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
private:// 合并有序链表ListNode *mergeList(ListNode *list1, ListNode *list2){ListNode *dummyhead = new ListNode(0);ListNode *cur = dummyhead;while(list1 && list2){if(list1->val <= list2->val){cur->next = list1;list1 = list1->next;}else{cur->next = list2;list2 = list2->next;}cur = cur->next;}cur->next = list1 ? list1 : list2;return dummyhead->next;}// 找到链表的中间节点ListNode *findMid(ListNode *head, ListNode *end){ListNode *fast=head, *slow=head;while(fast!=end && fast->next!=end){slow = slow->next;fast = fast->next->next;}return slow;}// 归并排序ListNode *mergeSort(ListNode *head, ListNode *end){// end_condif(!head) return head;if(head->next == end){head->next = nullptr;return head;} // find midListNode *mid = findMid(head, end);// groupListNode *list_l = mergeSort(head, mid);ListNode *list_r = mergeSort(mid, end);// mergereturn mergeList(list_l, list_r);}
public:// 以O(nlogn)时间复杂度, O(1)空间复杂度 排序链表ListNode *sortList(ListNode *head) {return mergeSort(head, nullptr);}
};
相关文章:
排序链表(归并排序)
148. 排序链表 - 力扣(LeetCode) 以O(nlogn)时间复杂度, O(1)空间复杂度 排序链表 涉及知识点: 找到链表的中间节点 2095. 删除链表的中间节点 - 力扣(LeetCode)合并有序链表 21. 合并两个有序链…...
Adobe After Effects的插件--------CC Particle World
CC Particle World是一个粒子效果器,用于在三维空间中生成和模拟各种粒子系统,包括火焰、雨、雪、爆炸、烟雾等等。它会自动随时间变化发射粒子。 本文部分参照 https://www.163.com/dy/article/IEJVDN760536FE6V.html 使用条件 使用该插件的图层需是2D图层。 我们新建一个…...
电脑硬盘数据丢失了怎么恢复?简单实用的硬盘数据找回的方法
我们的电脑使用硬盘作为存储设备来保存数据,硬盘里的数据是存储在扇区上,这些存储数据的单元则位于表面有磁性材料的旋转的盘片上。硬盘内部的磁头悬浮于高速旋转的盘片上,用于读写和检索数据。 假如我们使用电脑时不小心删除了某个文件&…...
k8s调度(pod亲和、反亲和、污点、容忍度)
pod亲和性 针对对象为Pod,目的是实现,新建Pod和目标Pod调度到一起,在同一个Node上。 示例: apiVersion: v1 kind: Pod metadata:name: testpod01labels:app: myapp01env: test1 spec:containers:- name: testpod01image: nginx:…...
智能制造核心领域:自动化、物联网、大数据分析、人工智能在现代制造业中的应用与融合
一、智能制造系统及领域 智能制造系统是一套集成的解决方案,它利用物联网(IoT)、大数据分析、人工智能(AI)、机器学习和云计算等技术,实现工厂和生产线的自动化、数据驱动和智能化。这些系统能够监控和控制…...
Android Studio 2024最新版Hello World
Android Studio 2024最新版Hello World 1. Android Studio 2024安装视频2. 创建项目Read Timed out 问题Android Studio Build Output 控制台中文乱码问题 3. 驱动管理 本文章介绍如何通过Android Studio 2024最新版创建项目, 并成功输出Hello World。 本次教程版本…...
请解释Java中的CountDownLatch和CyclicBarrier的区别和使用场景。什么是Java中的Semaphore?它如何控制并发访问?
请解释Java中的CountDownLatch和CyclicBarrier的区别和使用场景。 CountDownLatch 和 CyclicBarrier 是 Java 并发包(java.util.concurrent)中提供的两个非常有用的同步工具,它们都用于控制多个线程之间的同步,但它们的目的和使用…...
Django+Vue3前后端分离学习(五)(前端登录页面搭建)
1、如果需要使用组合式API,需要安装插件: npm install vite-plugin-vue-setup-extend --save-dev 在vite.config.js里配置: 首先导入: import VueSetupExtend from vite-plugin-vue-setup-extend 添加: 2、创建login.vue 然…...
虚拟机安装macos系统
虚拟机安装macOS系统是一个相对复杂但可行的过程,主要涉及前期准备、虚拟机软件安装、macOS镜像准备、虚拟机配置、系统安装及后续设置等多个步骤。以下是一个详细的教程,帮助您在虚拟机中成功安装macOS系统。 一、前期准备 1. 硬件要求 确保您的计算…...
AI基础 L9 Local Search II 局部搜索
Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时&#x…...
828华为云征文|使用sysbench对Mysql应用加速测评
文章目录 ❀前言❀测试环境准备❀测试工具选择❀测试工具安装❀mysql配置❀未开启Mysql加速测试❀开启Mysql加速测试❀总结 ❀前言 大家好,我是早九晚十二。 昨天有梳理一篇关于华为云最新推出的云服务器产品Flexus云服务器X。当时有说过,这次的华为云F…...
2024 年高教社杯全国大学生数学建模竞赛题目——D 题 反潜航空深弹命中概率问题的求解
2024 年高教社杯全国大学生数学建模竞赛题目 (请先阅读“ 全国大学生数学建模竞赛论文格式规范 ”) D 题 反潜航空深弹命中概率问题 应用深水炸弹(简称深弹)反潜,曾是二战时期反潜的重要手段,而随着现代军…...
【Kubernetes】常见面试题汇总(一)
目录 1.简述 etcd 及其特点? 2.简述 etcd 适应的场景? 3.简述什么是Kubernetes? 4.简述 Kubernetes和 Docker的关系? 1.简述 etcd 及其特点? (1)etcd 是Core0s 团队发起的开源项目…...
简单实用的php全新实物商城系统
免费开源电商系统,提供灵活的扩展特性、高度自动化与智能化、创新的管理模式和强大的自定义模块,让电商用户零成本拥有安全、高效、专业的移动商城。 代码是全新实物商城系统源码版。 代码下载...
Leetcode面试经典150题-128.最长连续序列-递归版本另解
之前写过一篇这个题的,但是可能代码比较复杂,这回来个简洁版的,这个是递归版本 可以看看之前的版本,两个版本面试用哪个都保过 解法都在代码里,不懂就留言或者私信 class Solution {/**对于之前的解法,我…...
spring security 中的授权使用
一、认证 身份认证,就是判断一个用户是否为合法用户的处理过程。Spring Security 中支持多种不同方式的认证,但是无论开发者使用那种方式认证,都不会影响授权功能使用。因为 SpringSecurity 很好做到了认证和授权解耦。 二、授权 授权&#x…...
python安装以及访问openAI API
安装python 我是python小白,所以需要一步一步来,先安装。 一口吃不成胖子,记住。 从官网下载python,目前最新版本是3.12,但是据说稳定版3.11更好一点,所以,下载3.11,注意不要下载…...
【Unity小技巧】URP管线遮挡高亮效果
前言 在URP渲染管线环境下实现物体遮挡高亮显示效果,效果如下:Unity URP遮挡高亮 实现步骤 创建层级,为需要显示高亮效果的物体添加层级,比如Player 创建一个材质球,也就是高亮效果显示的材质球找到Universal Render…...
C#中的GDI和GDI+(Graphics Device Interface Plus)图形设备接口
GDI的概念 GDI(Graphics Device Interface)是微软Windows操作系统中的一个组件,它提供了一组API,用于在显示器或打印机等图形设备上进行图形绘制和图像处理。GDI 是 Windows 编程中用于二维图形和图像处理的接口。 GDI 的主要功…...
谷粒商城のNginx
文章目录 前言一、Nginx1、安装Nginx2、相关配置2.1、配置host2.2、配置Nginx2.3、配置网关 前言 本篇重点介绍项目中的Nginx配置。 一、Nginx 1、安装Nginx 首先需要在本地虚拟机执行: mkdir -p /mydata/nginx/html /mydata/nginx/logs /mydata/nginx/conf在项目…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...
五子棋测试用例
一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏,有着深厚的文化底蕴。通过将五子棋制作成网页游戏,可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家,都可以通过网页五子棋感受到东方棋类…...
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10pip3.10) 一:前言二:安装编译依赖二:安装Python3.10三:安装PIP3.10四:安装Paddlepaddle基础框架4.1…...
用递归算法解锁「子集」问题 —— LeetCode 78题解析
文章目录 一、题目介绍二、递归思路详解:从决策树开始理解三、解法一:二叉决策树 DFS四、解法二:组合式回溯写法(推荐)五、解法对比 递归算法是编程中一种非常强大且常见的思想,它能够优雅地解决很多复杂的…...
