Leetcode : 147. 对链表进行插入排序

news/2024/4/15 4:23:12/文章来源:https://blog.csdn.net/weixin_44379563/article/details/136510600

给定单个链表的头 head ,使用 插入排序 对链表进行排序,并返回 排序后链表的头 。

插入排序 算法的步骤:

插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时,从输入数据中删除一个元素(红色),并就地插入已排序的列表中。

对链表进行插入排序。

思路:设置左右两对指针,分别负责比较和更改;相比于数组多了pre前置指针,用于修改链表的顺序。

#include <iostream>using namespace std;//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 {
// public:
//     ListNode* insertionSortList(ListNode* head) {
//         ListNode* slow = head;
//         ListNode* fast = head;
//         bool flag = false;
//         while (slow->next != NULL){
//             while (fast->next != NULL){
//                 if (fast->val > fast->next->val){
//                     ListnodeSwap(fast, fast->next);
//                     flag = true;
//                 }
//                 fast = fast->next;
//             }
//             if (flag == false) break;
//             fast = slow;
//             flag = false;
//         }
//         return head;
//     }
//     void ListnodeSwap(ListNode* a, ListNode* b){
//         int temp = a->val;
//         a->val = b->val;
//         b->val = temp;
//     }
// };class Solution {public:ListNode* insertionSortList(ListNode* head) {ListNode* root = new ListNode(0);ListNode* left_pre = root;left_pre->next = head;ListNode* left = head;ListNode* right = head->next;ListNode* right_pre = head;while (right != NULL){while (left->val <= right->val && left != right){left_pre = left;left = left->next;}if (left == right){right_pre = right;right = right->next;}else{right_pre->next = right->next;right->next = left;left_pre->next = right;if (left == head) head = right;right = right_pre->next;}left = head;left_pre = root;}return head;}
};int main(){Solution s;// ListNode* head = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));ListNode* head = new ListNode(-1, new ListNode(5, new ListNode(3, new ListNode(4, new ListNode(0)))));ListNode* res = s.insertionSortList(head);for (ListNode* i = res; i != NULL; i = i->next){cout << i->val << " ";}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_997062.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Java多线程——wait和notify方法作用,线程的状态

目录 引出wait和notify方法作用线程的状态创建线程有几种方式&#xff1f;方式1&#xff1a;继承Thread创建线程方式2&#xff1a;通过Runnable方式3&#xff1a;通过Callable创建线程方式4&#xff1a;通过线程池概述ThreadPoolExecutor API代码实现源码分析工作原理&#xff…

力扣刷题Days7第二题--242.有效的字母异位词(js)

目录 1&#xff0c;题目 2&#xff0c;代码 2.1 我思考完成的-初版--哈希表思想 2.2略改进 2.3排序思想 3&#xff0c;学习与总结 3.1 判断数组元素是否都为0 3.2总结 1&#xff0c;题目 给定两个字符串 s 和 t &#xff0c;编写一个函数来判断 t 是否是 s 的字母异位词…

okHttp MediaType MIME格式详解

一、介绍 我们在做数据上传时&#xff0c;经常会用到Okhttp的开源库&#xff0c;okhttp开源库也遵循html提交的MIME数据格式。 所以我们经常会看到applicaiton/json这样的格式在传。 但是如果涉及到其他文件等就需要详细的数据格式&#xff0c;否则服务端无法解析 二、okHt…

重学SpringBoot3-@EnableConfigurationProperties注解

重学SpringBoot3-EnableConfigurationProperties注解 1. 引言2. EnableConfigurationProperties 的作用3. 使用示例4. 总结 1. 引言 Spring Boot 提供了一种便捷的方式来管理和校验应用程序的配置&#xff0c;即通过类型安全的配置属性。EnableConfigurationProperties 注解在…

光谱整形1

华为张德江&#xff1a;下一代光传送网将走向400G80波WDM系统_通信世界网 (cww.net.cn) 张德江指出&#xff0c;400G WDM系统具有三大基本特征&#xff1a;支持400G80波&#xff0c;单纤32T超大容量&#xff0c;传输距离与100G相当&#xff1b;支持32维以上的光交叉&#xff1…

搜维尔科技:3D Systems Geomagic Design X 逆向工程软件

产品概述 3D Systems Geomagic Design X 是全面的逆向工程软件 GeomagicoDesign XTM是全面的逆向工程软件&#xff0c;它结合了基于特征的CAD数模与三维扫描数据处理&#xff0c;使您能创建出可编辑、基于特征的CAD数模&#xff0c;并与您现有的CAD软件兼容。 拓展您的设计能…

请说明Vue中的异步组件加载

Vue中的异步组件加载是指当页面需要渲染某个组件时&#xff0c;可以在需要时再去加载这个组件&#xff0c;而不是在页面初始化的时候就将所有组件一次性加载进来。这种方式能够有效降低页面的初始加载时间&#xff0c;提升用户体验。 在Vue中&#xff0c;我们可以使用import函…

springboot实现多线程开发(使用@Async注解,简单易上手)

根据springboot的核心思想便捷开发&#xff0c;使用多线程也变得简单起来&#xff0c;通过一下几个步骤即可实现。 核心注解 EnableAsync将此注解加在启动类上&#xff0c;使项目支持多线程。 Async 使用我们的Async注解在所需要进行多线程的类上即可实现。 配置线程池 …

从第一原理看大语言模型

大模型基础框架 大模型幻觉问题 大模型能力 思维链模式 思维链模式激发的是大模型的推理能力 LLM知识能力RAG

【设计模式】观察者模式及函数式编程的替代C++

本文介绍观察者模式以及使用函数式编程替代简单的策略模式。 观察者模式 观察者模式是一种行为型设计模式&#xff0c;它定义了一种一对多的依赖关系&#xff0c;当一个对象的状态发生改变时&#xff0c;其所有依赖者都会收到通知并自动更新。 当对象间存在一对多关系时&#…

day13_微服务监控Nginx(微服务集成SBA)

文章目录 1 微服务系统监控1.1 监控系统的意义1.2 SBA监控方案1.3 SBA实战1.3.1 创建SBA服务端1.3.2 微服务集成SBA 1.4 微服务集成logback1.5 配置邮件告警 2 Nginx2.1 Nginx简介2.2 下载和安装2.2.1 方式1&#xff1a;window本地安装2.2.1.1 下载2.2.1.2 安装2.2.1.3 目录结构…

【开源物联网平台】FastBee认证方式和MQTT主题设计

&#x1f308; 个人主页&#xff1a;帐篷Li &#x1f525; 系列专栏&#xff1a;FastBee物联网开源项目 &#x1f4aa;&#x1f3fb; 专注于简单&#xff0c;易用&#xff0c;可拓展&#xff0c;低成本商业化的AIOT物联网解决方案 目录 一、接入步骤 1.1 设备认证 1.2 设备交…

新项目,Linux上一键安装MySQL,Redis,Nacos,Minio

大家好&#xff0c;我是 jonssonyan 分享一个我的一个开源项目&#xff0c;这是一个在 Linux 平台上一键安装各种软件的脚本项目&#xff0c;脚本使用 Shell 语言编写&#xff0c;后续还会增加更多软件的一键安装&#xff0c;代码在 GitHub 上全部开源的&#xff0c;开源地址如…

TypeScript(三)对象,接口,类,泛型

一、 对象 Typescript 中 Object 类型不单是指普通对象类型&#xff0c;它泛指所有的非原始类型&#xff0c;也就是对象&#xff0c;数组还有函数。 普通对象就是键值对的集合&#xff0c;我们可以使用接口来定义对象的结构。interface Person { // Person是接口CHname: strin…

Python算法题集_搜索插入位置

Python算法题集_搜索插入位置 题51&#xff1a;搜索插入位置1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【二分法查找】2) 改进版一【二分法查找终止条件判断】3) 改进版二【第三方模块】 4. 最优算法5. 相关资源 本文为Python算法题集之一的…

基于springboot的智能物流管理系统论文

智能物流管理系统 摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了智能物流管理系统的开发全过程。通过分析智能物流管理系统管理的不足&#xff0c;创建了一个计算机管理智能物流管理系统的方案。文章介绍了智…

OpenCV与AI深度学习 | 基于OpenCV实现模糊检测 / 自动对焦

本文来源公众号“OpenCV与AI深度学习”&#xff0c;仅用于学术分享&#xff0c;侵权删&#xff0c;干货满满。 原文链接&#xff1a;基于OpenCV实现模糊检测 / 自动对焦 导 读 本文主要介绍使用OpenCV实现图像模糊检测/相机自动对焦功能。 前 言 为了检测图片是否对焦&…

深入浅出(二)MVVM

MVVM 1. 简介2. 示例 1. 简介 2. 示例 示例下载地址&#xff1a;https://download.csdn.net/download/qq_43572400/88925141 创建C# WPF应用(.NET Framework)工程&#xff0c;WpfApp1 添加程序集 GalaSoft.MvvmLight 创建ViewModel文件夹&#xff0c;并创建MainWindowV…

抖音视频评论批量采集软件|视频下载工具

《轻松搞定&#xff01;视频评论批量采集软件&#xff0c;助您高效工作》 在短视频这个充满活力和创意的平台上&#xff0c;了解用户评论是了解市场和观众心声的重要途径之一。为了帮助您快速获取大量视频评论数据&#xff0c;我们推出了一款操作便捷、功能强大的软件&#xff…

18个惊艳的可视化大屏(第20辑):物联网场景

实时监控和管理 物联网系统通常涉及大量的传感器、设备和数据&#xff0c;通过将这些数据可视化展示在大屏上&#xff0c;可以实时监控和管理物联网系统的运行状态。这有助于及时发现问题、快速响应&#xff0c;并提高系统的可靠性和稳定性。 数据分析和决策支持 可视化大屏可…