成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

[LintCode] Insertion Sort List

wzyplus / 2862人閱讀

摘要：插入排序維基百科一般來(lái)說(shuō)，插入排序都采用在數(shù)組上實(shí)現(xiàn)。在放這個(gè)數(shù)之前，這個(gè)數(shù)的目標(biāo)位置和原始位置之間的數(shù)都要先進(jìn)行后移。最后，當(dāng)，即遍歷完整個(gè)原鏈表之后，新鏈表排序完成。

Problem

Sort a linked list using insertion sort.

Example

Given 1->3->2->0->null, return 0->1->2->3->null.

Note

插入排序【維基百科】

一般來(lái)說(shuō)，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：

從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序

取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描

如果該元素（已排序）大于新元素，將該元素移到下一位置

重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置

將新元素插入到該位置后

重復(fù)步驟2~5

關(guān)于插入排序，我所知道的就是從頭部開(kāi)始，將每個(gè)數(shù)放到合適的位置。在放這個(gè)數(shù)之前，這個(gè)數(shù)的目標(biāo)位置和原始位置之間的數(shù)都要先進(jìn)行后移。然而這是一個(gè)in-place的操作，而對(duì)于鏈表而言，我們只要做一個(gè)空鏈表，然后不斷加入原鏈表中的最小元素即可。
cur是原鏈表head的指針，不斷向后掃描；node是空鏈表dummy的指針，用node.next與cur所指向的結(jié)點(diǎn)進(jìn)行比較，一旦發(fā)現(xiàn)排列好的新鏈表中有大于cur的結(jié)點(diǎn)，就把cur放在node.next，然后進(jìn)行下一輪循環(huán)：cur.next作為原鏈表新的cur，node返回新鏈表起點(diǎn)dummy。最后，當(dāng)cur = null，即遍歷完整個(gè)原鏈表之后，新鏈表排序完成。返回dummy.next即可。

Solution 
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode cur = head;
        while (cur != null) {
            ListNode node = dummy;
            while (node.next != null && node.next.val < cur.val) node = node.next;
            ListNode temp = cur.next;
            cur.next = node.next;
            node.next = cur;
            cur = temp;
        }
        return dummy.next;
    }
}

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65665.html

相關(guān)文章

  • [LintCode] Kth Largest Element [PriorityQueue]

    摘要：可以不要用太簡(jiǎn)單的方法。先把它裝滿，再和隊(duì)列頂端的數(shù)字比較，大的就替換掉，小的就。遍歷完所有元素之后，頂部的數(shù)就是第大的數(shù)。 Problem Find K-th largest element in an array. Example In array [9,3,2,4,8], the 3rd largest element is 4.In array [1,2,3,4,5], the...

    Hwg 評(píng)論0 收藏0

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

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

    Brenner 評(píng)論0 收藏0

  • 147. Insertion Sort List

    注意新的list跟原來(lái)的list是不相連的，然后把各個(gè)狀態(tài)的點(diǎn)記錄好就行： public ListNode insertionSortList(ListNode head) { if (head == null || head.next == null) return head; //We started a new list here, not ...

    codeGoogle 評(píng)論0 收藏0

  • [LintCode] Sort List [分治]

    摘要：這道題目可以用分治法來(lái)做，首先從鏈表中點(diǎn)分割鏈表，然后將兩個(gè)鏈表重新排序并合并。 Problem Sort a linked list in O(n log n) time using constant space complexity. Example Given 1-3->2->null, sort it to 1->2->3->null. Note 這道題目可以用分治法來(lái)做，首先...

    Shisui 評(píng)論0 收藏0

  • LintCode547/548_求數(shù)組交集不同解法小結(jié)

    摘要：求數(shù)組交集不同解法小結(jié)聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處求數(shù)組交集要求元素不重復(fù)，給出兩個(gè)數(shù)組，求二者交集且元素不重復(fù)，查找會(huì)超時(shí)解法一排序二分查找算法超時(shí)主要發(fā)生在大數(shù)組查找過(guò)程，因此采用二分查找提升查找效率，交集用保存實(shí)現(xiàn)去重解法 LintCode547/548_求數(shù)組交集不同解法小結(jié) [TOC] 聲明 文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處：[1] https://segme...

    gxyz 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<