[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)


相关推荐

  • gitlab 升级_gitlab回退到指定版本

    gitlab 升级_gitlab回退到指定版本GitLab跨版本升级

  • Java编程语言简单常用的输入输出格式

    Java编程语言简单常用的输入输出格式Java语言和C语言的输入输出不同。C语言直接使用scanf()函数进行输入,使用printf()函数进行输出。而在Java中,所谓的函数有了一个新的名词,叫做方法。输入输出方法并不能想C语言那样可以默认直接使用。在使用前需要进行import进行类的导入,然后再进行方法的调用。具体实现,我们可以结合一段简单的代码来解释说明。源码如下:importjava.util.Scanner;publ…

  • angular 路由懒加载_angular路由

    angular 路由懒加载_angular路由angular8路由懒加载在angular中路由即能加载组件又能加载模块,而我们说的懒加载实际上就是加载模块,目前还没有看到懒加载租价的例子。加载组件使用的是component关键字加载模块则是使用loadChildren关键字例子代码父模块路由文件import{NgModule}from’@angular/core’;import{Routes,RouterMo…

  • java快捷键

    java快捷键快捷键:如果想修改快捷键(setting->keymap)。Ctrl+Space完成类、方法、变量名称的自动输入,这个快捷键是我最经常使用的快捷键了,它可以完成类、方法、变量名称的自动录入,很方便Ctrl+N(Ctrl+Shift+N)跳转到指定的java文件(其它文件)这个功能很方便,至少我不用每回都在一长串的文件列表里找寻我想要编辑的类文件和jsp文件了Ctrl+B跳转到定义处这个就不用多说了,好象是个IDE就会提供的功能Ctrl+Alt+T用*来围绕

  • VIM查找关键字方法「建议收藏」

    VIM查找关键字方法「建议收藏」单击“Ctrl”+”:”进入命令行模式打“/”+“关键字”回车就可以查找了上一个匹配:”N“,下一个匹配:”n”(next)

  • teamviwer-无限绑定

    teamviwer-无限绑定

发表回复

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

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