资讯专栏INFORMATION COLUMN

147. Insertion Sort List

codeGoogle / 1329人阅读

注意新的list跟原来的list是不相连的,然后把各个状态的点记录好就行:

public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;
        
        //We started a new list here, not the original one
        ListNode dummy = new ListNode(0);
        ListNode curt = head, prev = dummy, next = head;
        while (curt != null) {
            next = curt.next;
            
            while (prev.next != null && prev.next.val < curt.val) {
                prev = prev.next;
            }
            
            curt.next = prev.next;
            prev.next = curt;
            curt = next;
            prev = dummy;
        }
        
        return dummy.next;
    }

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/64841.html

相关文章

  • Insertion Sort List,Merge Two Sorted Lists,Sort Li

    摘要:解题思路题目很简单,就是要求用插入排序的方法来为链表排序。插入排序就是每次遍历一个新的元素,将其插入到前面已经排好序的元素中。但要注意我们要将的前一个节点记录下来在找到中点后,我们要将这样链表才能分割成个。 Insertion Sort ListSort a linked list using insertion sort. 1.解题思路 题目很简单,就是要求用插入排序的方法来为链表排...

    Brenner 评论0 收藏0
  • [LintCode] Insertion Sort List

    摘要:插入排序维基百科一般来说,插入排序都采用在数组上实现。在放这个数之前,这个数的目标位置和原始位置之间的数都要先进行后移。最后,当,即遍历完整个原链表之后,新链表排序完成。 Problem Sort a linked list using insertion sort. Example Given 1->3->2->0->null, return 0->1->2->3->null. No...

    wzyplus 评论0 收藏0
  • 基础排序算法

    摘要:递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。算法实现实现分配排序计数排序计数排序与之前的算法采用的是完全不同的一种视角,它注重的是元素应该存在的位置,而不再是两个元素之间的大小关系。 原文链接:http://kasheemlew.github.io/2... 简单排序 插入排序 想象一下插队的过程... showImg(https://segmentfault.com/...

    W_BinaryTree 评论0 收藏0
  • Sorting

    摘要:是稳定的排序,但是它需要额外的空间,时间复杂度为程序这个同上也是两个步骤,。最坏情况的时间复杂度为但是在实际情况中,通常是排序的最佳选择。就是有序的完全二叉树,所有我们要先根据已有的数组来建立一个。最后由后往前形成一个有序数组。 Bubble Sort就不说了,下面简单总结一个Selection Sort, Insertion Sort, Merge Sort和Quick Sort: ...

    calx 评论0 收藏0
  • 基本排序 - Algorithms, Part I, week 2 ELEMENTARY SORTS

    摘要:我们讨论比较排序算法的理论基础,并结合本章应用排序和优先级队列算法。基本排序引入了选择排序,插入排序和。描述了,一种保证在线性时间内运行的排序算法。当我们后续实现排序算法时,我们实际上将这个机制隐藏在我们的实现下面。 前言 上一篇:栈和队列下一篇:归并排序 排序是重新排列一系列对象以便按照某种逻辑顺序排列的过程。排序在商业数据处理和现代科学计算中起着重要作用。在交易处理,组合优化,天体...

    BLUE 评论0 收藏0

发表评论

0条评论

codeGoogle

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<