题目描述
难度:Middle
相关话题:排序
、链表
对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始,该链表可以被认为已经部分排序(用黑色表示)。
每次迭代时,从输入数据中移除一个元素(用红色表示),并原地将其插入到已排好序的链表中。
插入排序算法:
- 插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
-
每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
-
重复直到所有输入数据插入完为止。
示例 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;
};
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com