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)


相关推荐

  • 安防监控必备的基础知识「建议收藏」

    安防监控必备的基础知识「建议收藏」安防监控必备的基础知识 什么是云镜控制解码器?答:解码器是将前端发出的控制信号转换为电压信号从而控制云台、镜头的的装置。什么是同轴电缆?答:同轴电缆(COARIALCABLE)的得名与它的结构相关。同轴电缆也是监控中最常见的传输介质之一。它用来传递信息的一对导体是按照一层圆筒式的外导体套在内导体(一根细芯)外面,两个导体间用绝缘材料互相隔离的结构制选的,外层导体和中心轴芯线的…

  • 舵机内部结及工作原理浅析[通俗易懂]

    舵机内部结及工作原理浅析[通俗易懂]一、舵机实物图就像上面这张照片,相信大家都不会陌生,我们常见到的舵机就是这个模样,一般是塑料外壳,当然很少见的也有金属外壳的舵机,因为涉及到控制信号,所以一般有三条引出线。像上图所示的样子,舵机有一个三线的接口。黑色线(或棕色线)是接地线,红线接+5V电压,黄线(或是白色或橙色)接控制信号端。(而步进电机一般会有4~6根不等的引出线)二…

  • navcat 激活码(JetBrains全家桶)

    (navcat 激活码)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.htmlMLZPB5EL5Q-eyJsaWNlbnNlSW…

  • vue环境安装与配置(Linux安装常用开发工具)

    vue安装环境搭建提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档文章目录vue安装环境搭建前言一、node.js安装和配置1.下载安装node.js2.配置默认安装目录和缓存日志目录3.node.js环境配置4.配置淘宝镜像源二、使用步骤1.引入库2.读入数据总结前言vue前端框架的环境搭建一、node.js安装和配置1.下载安装node.js官网下载最新版本:https://nodejs.org/en/download/可以下载安装包(安装教程见:http

  • [LeetCode] Top K Frequent Elements 前K个高频元素

    [LeetCode] Top K Frequent Elements 前K个高频元素

  • Redis创建高可用集群教程【Windows环境】

    模仿的过程中,加入自己的思考和理解,也会有进步和收获。在这个互联网时代,在高并发和高流量可能随时爆发的情况下,单机版的系统或者单机版的应用已经无法生存,越来越多的应用开始支持集群,支持分布式部署了。而Redis作为缓存服务器的比较出色的一员,它在出生的时候就被设置支持集群,本篇就是介绍Redis集群的介绍和搭建过程!使用的平台是Windows,搭建的思路和Linux上基本一致! 墙…

发表回复

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

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