[LeetCode] Insertion Sort List 链表插入排序「建议收藏」

[LeetCode] Insertion Sort List 链表插入排序

大家好,又见面了,我是全栈君。

Sort a linked list using insertion sort.

链表的插入排序实现原理很简单,就是一个元素一个元素的从原链表中取出来,然后按顺序插入到新链表中,时间复杂度为O(n2),是一种效率并不是很高的算法,但是空间复杂度为O(1),以高时间复杂度换取了低空间复杂度。代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        ListNode *res = new ListNode(-1);
        ListNode *cur = res;
        while (head) {
            ListNode *next = head->next;
            cur = res;
            while (cur->next && cur->next->val <= head->val) {
                cur = cur->next;
            }
            head->next = cur->next;
            cur->next = head;
            head = next;
        }
        return res->next;
    }
};

本文转自博客园Grandyang的博客,原文链接:链表插入排序[LeetCode] Insertion Sort List ,如需转载请自行联系原博主。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107859.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • pnp和npn开关电路区别图解_npn和pnp工作原理

    pnp和npn开关电路区别图解_npn和pnp工作原理模拟电路学的不好的我,遇到“管子”就有一种莫名的恐惧,一点也不想分析电路原理,只想知道这个“管子”用在这里起的啥作用,仅此就够了。三极管就是这样一种让我又爱又恨的“管子”,在我设计的电路中,用的还真的不少,每次都要查查是NPN还是PNP,低电平有效还是高电平有效。但是网络上的文章分析的对我来说都太复杂,所以想自己做一个SOP,记住最简单的用法就行了。最近分析一个电路,里面涉及到的主要是三…

  • idea常用快捷键分享|IntelliJ IDEA快捷键分享

    idea常用快捷键分享|IntelliJ IDEA快捷键分享前言idea工具确实好用,从eclipse到idea,永无回头路,从破解到开源license,无法逃脱真想定律。现在列举出如下快捷键,让你在idea中如鱼得水。一、Ctrl快捷键Ctrl+F在当前文件进行文本查找(必备)Ctrl+R在当前文件进行文本替换(必备)Ctrl+Z撤销(必备) Ctrl+Y删除光标所在行或删除选中的行(必备)Ctrl+X剪切光标所在行或剪切选择内容Ctrl+C复制光标所在行

  • mysql报错日志文件在哪_windows硬件报错日志

    mysql报错日志文件在哪_windows硬件报错日志1.cmd打开服务,找到mysql服务,查看属性中my.ini配置文件所在位置:2.打开my.ini配置文件,查看datadir配置:datadir=C:/ProgramData/MySQL/MySQLServer5.7/Data此目录存储了错误日志文件3.查看错误日志文件名SHOWVARIABLESLIKE”%error%”;…

    2022年10月13日
  • 怎样从数组中删除给定元素_java数组包含某个元素

    怎样从数组中删除给定元素_java数组包含某个元素packageday21;importjava.util.Scanner;//调用Scanner一个简单的文本扫描器importstaticnet.mindview.util.Print.*;importjava.util.Random;publicclassShow{publicstaticvoidmain(String[]args){int[]a={0,1,2,3};for(inti:a).

  • 华为verilog代码规范(wps初学者入门教程)

    对于初学者,可大致了解VerologHDL所提供的能力,掌握VerilogHDL语言的核心子集。1VerilogHDL语言具有:设计的行为特性、设计的数据流特性、设计的结构组成以及包括响应监控和设计验证方面的时延和波形产生机制。2如何描述自顶向下的设计思想:每个模块实现特定的功能,模块间可进行层次的嵌套,因此可以将大型的数字电路设计分割成大小不一的小模块来实现特定的功能,最后通过由顶层模块调用子模块来实现整体功能。3三种建模方式3.1结构化描述方式结构化建模方式就是通过对电

  • pandas.read_csv() 报错 OSError: Initializing from file failed,报错原因分析和解决方法

    pandas.read_csv() 报错 OSError: Initializing from file failed,报错原因分析和解决方法pandas.read_csv()报错OSError:Initializingfromfilefailed,一般由两种情况引起:一种是函数参数为路径而非文件名称,另一种是函数参数带有中文。

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号