147. Insertion Sort List

codeGoogle 發(fā)布于2019-08-14 14:09 / 1476人閱讀

注意新的list跟原來的list是不相連的，然后把各個狀態(tài)的點記錄好就行：

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;
    }

云服務(wù)器 GPU云服務(wù)器 insertion-sort Insertion sort() sort

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/64841.html

相關(guān)文章

Insertion Sort List,Merge Two Sorted Lists,Sort Li

摘要：解題思路題目很簡單，就是要求用插入排序的方法來為鏈表排序。插入排序就是每次遍歷一個新的元素，將其插入到前面已經(jīng)排好序的元素中。但要注意我們要將的前一個節(jié)點記錄下來在找到中點后，我們要將這樣鏈表才能分割成個。 Insertion Sort ListSort a linked list using insertion sort. 1.解題思路題目很簡單，就是要求用插入排序的方法來為鏈表排...

Brenner 2019-08-16 10:27 評論0 收藏0
[LintCode] Insertion Sort List

摘要：插入排序維基百科一般來說，插入排序都采用在數(shù)組上實現(xiàn)。在放這個數(shù)之前，這個數(shù)的目標(biāo)位置和原始位置之間的數(shù)都要先進行后移。最后，當(dāng)，即遍歷完整個原鏈表之后，新鏈表排序完成。 Problem Sort a linked list using insertion sort. Example Given 1->3->2->0->null, return 0->1->2->3->null. No...

wzyplus 2019-08-14 15:21 評論0 收藏0
基礎(chǔ)排序算法

摘要：遞歸地把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。算法實現(xiàn)實現(xiàn)分配排序計數(shù)排序計數(shù)排序與之前的算法采用的是完全不同的一種視角，它注重的是元素應(yīng)該存在的位置，而不再是兩個元素之間的大小關(guān)系。原文鏈接：http://kasheemlew.github.io/2... 簡單排序插入排序想象一下插隊的過程... showImg(https://segmentfault.com/...

W_BinaryTree 2019-07-25 11:41 評論0 收藏0
Sorting

摘要：是穩(wěn)定的排序，但是它需要額外的空間，時間復(fù)雜度為程序這個同上也是兩個步驟，。最壞情況的時間復(fù)雜度為但是在實際情況中，通常是排序的最佳選擇。就是有序的完全二叉樹，所有我們要先根據(jù)已有的數(shù)組來建立一個。最后由后往前形成一個有序數(shù)組。 Bubble Sort就不說了，下面簡單總結(jié)一個Selection Sort, Insertion Sort, Merge Sort和Quick Sort: ...

calx 2019-08-14 14:09 評論0 收藏0
基本排序 - Algorithms, Part I, week 2 ELEMENTARY SORTS

摘要：我們討論比較排序算法的理論基礎(chǔ)，并結(jié)合本章應(yīng)用排序和優(yōu)先級隊列算法?；九判蛞肓诉x擇排序，插入排序和。描述了，一種保證在線性時間內(nèi)運行的排序算法。當(dāng)我們后續(xù)實現(xiàn)排序算法時，我們實際上將這個機制隱藏在我們的實現(xiàn)下面。前言上一篇：棧和隊列下一篇：歸并排序排序是重新排列一系列對象以便按照某種邏輯順序排列的過程。排序在商業(yè)數(shù)據(jù)處理和現(xiàn)代科學(xué)計算中起著重要作用。在交易處理，組合優(yōu)化，天體...

BLUE 2019-08-16 15:58 評論0 收藏0