leetcode做题笔记148. 排序链表
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
思路一:归并排序
c语言解法
struct ListNode* merge(struct ListNode* head1, struct ListNode* head2) {struct ListNode* dummyHead = malloc(sizeof(struct ListNode));dummyHead->val = 0;struct ListNode *temp = dummyHead, *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 dummyHead->next;
}struct ListNode* toSortList(struct ListNode* head, struct ListNode* tail) {if (head == NULL) {return head;}if (head->next == tail) {head->next = NULL;return head;}struct ListNode *slow = head, *fast = head;while (fast != tail) {slow = slow->next;fast = fast->next;if (fast != tail) {fast = fast->next;}}struct ListNode* mid = slow;return merge(toSortList(head, mid), toSortList(mid, tail));
}struct ListNode* sortList(struct ListNode* head) {return toSortList(head, NULL);
}
分析:
本题要将链表排序,由于链表的特性,无法直接从中间进行修改,所以利用快慢指针将链表分为两部分,对两个子链表进行排序,通过递归不断将链表分为两部分,直到无法分为止,最后合并所有的链表,得到排序后的链表
思路二:转换为数组后进行排序再转换为链表
c语言解法(此解法有取巧的成分,但时间复杂度上优于思路一,故列出)
int cmp(const int* a,const int* b)
{return *(int*)a - *(int*)b;
}struct ListNode* sortList(struct ListNode* head)
{int A[50000]={0};int i = 0;struct ListNode* tmp = head;for(i=0; tmp != NULL; i++){A[i] = tmp->val;tmp = tmp->next;}qsort(A,i,sizeof(int),cmp);tmp = head;for(i=0; tmp != NULL;i++){tmp->val = A[i];tmp = tmp->next;}return head;
}
分析:
第二种思路则是将原链表转换为数组后进行排序再转换为链表,此解法更加直观,同时数组排序更加熟悉,此处利用快速排序排序数组,最后返回排序好的链表即可解决
总结:
本题考察对链表的排序操作,利用归并排序即可解决,也可转换为数组后利用数组的方法解决。
相关文章:
leetcode做题笔记148. 排序链表
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。 思路一:归并排序 c语言解法 struct ListNode* merge(struct ListNode* head1, struct ListNode* head2) {struct ListNode* dummyHead malloc(sizeof(struct ListNode));dummyHead…...
多线程学习
并发:交替运行 并行:一起运行 多线程实现方式 继承Thread类 ①自己定义一个类继承Thread public class MyThread extends Thread{public void run(){}} ②重写run方法 public class MyThread extends Thread{public void run(){"重写的内容&…...
软件测试/测试开发丨ChatGPT在测试计划中的应用策略
点此获取更多相关资料 简介 测试计划是指描述了要进行的测试活动的范围、方法、资源和进度的文档。它主要包括测试项、被测特性、测试任务和风险控制等。 所以在使用ChatGPT输出结果之前,我们需要先将文档的内容框架梳理好,以及将内容范围划定好&…...
链表oj3(Leetcode)——相交链表;环形链表
一,相交链表 相交链表(Leetcode) 1.1分析 看到这个我们首先想到的就是一个一个比较他们的值有相等的就是交点,但是如果a1和b2的值就相等呢?所以这个思路不行,第二种就是依次比较链表,但是这…...
nginx反向代理
nginx反向代理8.反向代理8.1 实现http反向代理8.1.1 反向代理配置参数8.1.2 反向代理单台web服务器8.1.2.1 端口号后加"/"8.1.2.2 端口号后不加"/" 8.1.3指定location 实现反向代理,动静分离8.1.4 反向代理实例:缓存功能8.1.4.1 举例 8.1.5 实现…...
基于eBPF的安卓逆向辅助工具——stackplz
前言 stackplz是一款基于eBPF技术实现的追踪工具,目的是辅助安卓native逆向,仅支持64位进程,主要功能如下: hardware breakpoint 基于pref_event实现的硬件断点功能,在断点处可读取寄存器信息,不会被用户…...
十大排序——4.堆排序
前面我们讲了堆,现在我们来看一下队排序。 堆排序的步骤: 首先将一个无序数组建立成一个大顶堆然后,将堆顶的元素和堆低的元素进行交换(即将最大的元素交换的到堆底),缩小并下潜调整堆重复上一步…...
独辟蹊径”之动态切换进程代理IP
前言 项目中遇到这样一个需求,需要动态切换指定进程Sockets5代理IP,目前了解到可通过编写驱动拦截或者劫持LSP实现,LSP劫持不太稳定,驱动无疑是相对较好的解决方案,奈何水平不足便有了这"蹊径"。 初步尝试…...
redis漏洞修复:(CNVD-2019-21763)
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、漏洞内容二、镜像准备1.确认镜像版本2.下载镜像 三、配置文件准备1.获取配置文件2.修改配置文件 四、启动redis容器五、修改iptables文件总结 前言 漏扫发…...
手刻 Deep Learning -第壹章-PyTorch入门教学-基础概念与再探线性回归
一、前言 本章会需要 微分、线性回归与矩阵的基本观念 这次我们要来做 PyTorch 的简单教学,我们先从简单的计算与自动导数( auto grad / 微分 )开始,使用优化器与误差计算,然后使用 PyTorch 做线性回归,还有…...
深入学习 Redis - 如何使用 Redis 作缓存?缓存更新策略?使用需要注意哪些问题(工作/重点)
目录 一、Redis 作为缓存 1.1、缓存的基本概念 1.1.1、理解 1.1.2、缓存存什么样的数据?二八定律 1.2、如何使用 redis 作为缓存 1.3、缓存更新策略(redis 内存淘汰机制 / 重点) 1.3.1、定期生成 1.3.2、实时生成 内存淘汰策略&#…...
好用的软件测试框架有哪些?测试框架的作用是什么?
软件测试框架是现代软件开发过程中至关重要的工具,它可以帮助开发团队更加高效地进行测试和验证工作,从而大大提高软件质量和用户体验。 一、好用的软件测试框架 1. Selenium:作为一种开源的自动化测试框架,Selenium具有功能强大…...
PAT 1035 插入与归并
PAT 1035 插入与归并 题目描述思路讲解代码展示 题目描述 思路讲解 分析:先将i指向中间序列中满足从左到右是从小到大顺序的最后一个下标,再将j指向从i1开始,第一个不满足a[j] b[j]的下标,如果j顺利到达了下标n,说明…...
K-means 聚类算法学习笔记
K-means 聚类算法 是一种无监督学习算法,用来将 n n n 个样本点分成 k k k 类,使得整个数据集的误差平方和 S S E SSE SSE 最小。在本例中,样本点是指平面直角坐标系上的点,聚类中心也是平面直角坐标系上的点,而每个…...
API文档搜索引擎
导航小助手 一、认识搜索引擎 二、项目目标 三、模块划分 四、创建项目 五、关于分词 六、实现索引模块 6.1 实现 Parser类 6.2 实现 Index类 6.2.1 创建 Index类 6.2.2 创建DocInfo类 6.2.3 创建 Weight类 6.2.4 实现 getDocInfo 和 getInverted方法 6.2.5 实现 …...
文案内容千篇一律,软文推广如何加深用户印象
随着互联网技术的发展,企业营销的方式逐渐转向软文推广,但是现在软文推广的内容同质化越来越严重,企业应该如何让自己的软文推广保持差异性,在用户心中留下独特的印象呢?下面就让媒介盒子告诉你。 一、 找出产品独特卖…...
十二、流程控制-循环
流程控制-循环 1.while循环语句★2.do...while语句★3.for循环语句 —————————————————————————————————————————————————— 1.while循环语句★ while语句也称条件判断语句,它的循环方式是利用一个条件来控制是否…...
五、回溯(trackback)
文章目录 一、算法定义二、经典例题(一)排列1.[46.全排列](https://leetcode.cn/problems/permutations/description/)(1)思路(2)代码(3)复杂度分析 2.[LCR 083. 全排列](https://le…...
什么是分布式锁?他解决了什么样的问题?
相信对于朋友们来说,锁这个东西已经非常熟悉了,在说分布式锁之前,我们来聊聊单体应用时候的本地锁,这个锁很多小伙伴都会用 ✔本地锁 我们在开发单体应用的时候,为了保证多个线程并发访问公共资源的时候,…...
Ubuntu 12.04增加右键命令:在终端中打开增加打开文件
Ubuntu 12.04增加右键命令:在终端中打开 软件中心:搜索nautilus-open-terminal安装 用快捷键CtrlT打开命令行输入: sudo apt-get install nautilus-open-terminal 重新加载文件管理器 nautilus -q 或注销再登录即要使用...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...
力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...
STM32---外部32.768K晶振(LSE)无法起振问题
晶振是否起振主要就检查两个1、晶振与MCU是否兼容;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容(CL)与匹配电容(CL1、CL2)的关系 2. 如何选择 CL1 和 CL…...
小木的算法日记-多叉树的递归/层序遍历
🌲 从二叉树到森林:一文彻底搞懂多叉树遍历的艺术 🚀 引言 你好,未来的算法大神! 在数据结构的世界里,“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的,它…...
比特币:固若金汤的数字堡垒与它的四道防线
第一道防线:机密信函——无法破解的哈希加密 将每一笔比特币交易比作一封在堡垒内部传递的机密信函。 解释“哈希”(Hashing)就是一种军事级的加密术(SHA-256),能将信函内容(交易细节…...
