1. 首页

LeetCode 147. 对链表进行插入排序

题目描述

难度:Middle

相关话题:排序链表

对链表进行插入排序。

LeetCode 147. 对链表进行插入排序

插入排序的动画演示如上。从第一个元素开始,该链表可以被认为已经部分排序(用黑色表示)。
每次迭代时,从输入数据中移除一个元素(用红色表示),并原地将其插入到已排好序的链表中。

插入排序算法:

  1. 插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。

  2. 每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。

  3. 重复直到所有输入数据插入完为止。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

思路:

定义一个空节点root,我们要做的就是维护这个空节点之后的所有节点都是有序的。

head中每一个节点遍历检查,检查这个节点应该在root中的位置,并且将它插入位置中。

当检查完毕,root后面的节点就是一个有序节点。

/**
 * @ Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var insertionSortList = function(head) {
        if( head == null ){
            return head;
        }

        let helper = new ListNode(0); //new starter of the sorted list
        let cur = head; //the node will be inserted
        let pre = helper; //insert node between pre and pre.next
        let next = null; //the next node will be inserted
        //not the end of input list
        while( cur != null ){
            next = cur.next;
            //find the right place to insert
            while( pre.next != null && pre.next.val < cur.val ){
                pre = pre.next;
            }
            //insert between pre and pre.next
            cur.next = pre.next;
            pre.next = cur;
            pre = helper;
            cur = next;
        }

        return helper.next;

};

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 147. 对链表进行插入排序

链接:https://www.javascriptc.com/4511.html

« use-what-changed 源码
LeetCode 148. 排序链表»
Flutter 中文教程资源

相关推荐

QR code