leetcode, LC5: insertion-sort-list[通俗易懂]

leetcode, LC5: insertion-sort-list[通俗易懂]题目描述使用插入排序对链表进行排序。Sortalinkedlistusinginsertionsort.示例1输入{3,2,4}输出{2,3,4}解题思路new一个新的ListNode作为选择排序好的链表的表头对于原始链表中的每一个结点2.1.寻找新链表中该结点的插入位置2.2插入该结点返回新链表代码实现/***structListNode{* intval;* structListNode*next;

大家好,又见面了,我是你们的朋友全栈君。

题目描述

使用插入排序对链表进行排序。
Sort a linked list using insertion sort.

示例1

输入

{3, 2, 4}

输出

{2, 3, 4}

解题思路

  1. new 一个新的 ListNode 作为选择排序好的链表的表头
  2. 对于原始链表中的每一个结点
    2.1. 寻找新链表中该结点的插入位置
    2.2 插入该结点
  3. 返回新链表

代码实现

/** * struct ListNode { * int val; * struct ListNode *next; * }; */

class Solution { 
   
public:
    /** * * @param head ListNode类 * @return ListNode类 */
    ListNode* insertionSortList(ListNode* head) { 
   
        // write code here
        if(head == NULL || head->next == NULL) return head;
        
        ListNode* currNode;
        ListNode* retLListHead = new ListNode(0);
        ListNode* retLListCurrNodeLast;
        ListNode* retLListCurrNode;
        while(head){ 
   
            currNode = head;
            retLListCurrNodeLast = retLListHead;
            retLListCurrNode = retLListCurrNodeLast->next;
            head = head->next;
            while(retLListCurrNode && retLListCurrNode->val < currNode->val){ 
   
                retLListCurrNodeLast = retLListCurrNodeLast->next;
                retLListCurrNode = retLListCurrNode->next;
            }
            currNode->next = retLListCurrNode;
            retLListCurrNodeLast->next = currNode;
        }
        return retLListHead->next;
    }
};

运行结果

运行时间:27ms
占用内存:632k

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

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

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

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

(0)


相关推荐

  • ubuntu server 文件共享

    ubuntu server 文件共享

  • linux修改nginx端口_nginx默认配置文件

    linux修改nginx端口_nginx默认配置文件我们都知道nginx默认使用80端口,有时候我们希望nginx运行在其他端口,就需要更改nginx配置nginx配置文件在/etc/nginx目录下的nginx.conf。在nginx.conf->http选项末尾有引入两个目录下的文件分别为:http{#省略部分内容include/etc/nginx/conf.d/*.con

  • afc2add是什么_appsync怎么使用

    afc2add是什么_appsync怎么使用APPsync是iPhone、iPad、iPodtouch越狱后最常安装的补丁,安装后可以绕过系统验证,随意安装运行破解的ipa软件。软件类型:Cydia软件软件格式:deb对于…

  • python取整符号_python 取整「建议收藏」

    广告关闭腾讯云11.11云上盛惠,精选热门产品助力上云,云服务器首年88元起,买的越多返的越多,最高返5000元!(1)向下取整向下取整很简单,直接使用int()函数即可,如下代码(python2.7.5idle)a=3.75int(a)3(2)四舍五入第二种就是对数字进行四舍五入,具体的看下面的代码:a=3.25;b=3.75round(a);round(b)3.0…

  • es集群搭建_k8s和docker搭建es集群

    es集群搭建_k8s和docker搭建es集群单机的elasticsearch做数据存储,必然面临两个问题:海量数据存储问题、单点故障问题。ES集群搭建_使用docker-海量数据存储问题:将索引库从逻辑上拆分为N个分片(shard),存储到多个节点-单点故障问题:将分片数据在不同节点备份(replica)ES集群介绍为什么需要集群ES集群相关概念搭建ES集群集群职责划分集群脑裂问题…

    2022年10月12日
  • UE4地编基础-材质蓝图篇[通俗易懂]

    UE4地编基础-材质蓝图篇[通俗易懂]一、贴图规格颜色贴图:颜色贴图必须是8位数RGB颜色。如果在UE4里,发现颜色贴图泛白,那么明颜色贴图是16位数的。改成8位数就正常了。灰度贴图:包括AO、Metallic(金属度)、Roughness(粗糙度)贴图。法线贴图:UE4支持Directx的法线贴图。二、贴图效果调节(蓝图)法线贴图强度调节:AO贴图强度调节:三、各种材质制作1、玻璃材质2、自发光材质……

发表回复

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

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