国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LintCode] Sort List [分治]

Shisui / 3125人閱讀

摘要：這道題目可以用分治法來做，首先從鏈表中點分割鏈表，然后將兩個鏈表重新排序并合并。

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

這道題目可以用分治法來做，首先從鏈表中點分割鏈表，然后將兩個鏈表重新排序并合并。

Solution 
public class Solution {
    public ListNode sortList(ListNode head) {  
        if (head == null || head.next == null) return head;
        ListNode mid = findMid(head);
        ListNode n2 = sortList(mid.next);
        mid.next = null;
        ListNode n1 = sortList(head);
        return merge(n1, n2);
    }
    public ListNode findMid(ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    public ListNode merge(ListNode n1, ListNode n2) {
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        while (n1 != null && n2 != null) {
            if (n1.val < n2.val) {
                head.next = n1;
                n1 = n1.next;
            }
            else {
                head.next = n2;
                n2 = n2.next;
            }
            head = head.next;
        }
        if (n1 != null) head.next = n1;
        else head.next = n2;
        return dummy.next;
    }
}

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

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/65829.html

相關(guān)文章

  • [LintCode] Merge K Sorted Lists [DC/Heap]

    摘要：分治做法中，函數(shù)依然是將鏈表結(jié)點兩兩進行比較，然后在函數(shù)中迭代兩個二分后的結(jié)果。 Problem Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example Given lists: [ 2->4->null, null, ...

    happyhuangjinjin 評論0 收藏0

  • [LintCode] Insertion Sort List

    摘要：插入排序維基百科一般來說，插入排序都采用在數(shù)組上實現(xiàn)。在放這個數(shù)之前，這個數(shù)的目標位置和原始位置之間的數(shù)都要先進行后移。最后，當，即遍歷完整個原鏈表之后，新鏈表排序完成。 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

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

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

    gxyz 評論0 收藏0

  • [LeetCode/LintCode] Merge Intervals

    摘要：方法上沒太多難點，先按所有區(qū)間的起點排序，然后用和兩個指針，如果有交集進行操作，否則向后移動。由于要求的，就對原數(shù)組直接進行操作了。時間復(fù)雜度是的時間。 Problem Given a collection of intervals, merge all overlapping intervals. Example Given intervals => merged intervals...

    gougoujiang 評論0 收藏0

  • [Lintcode] Find Peak Element 找峰值

    摘要：找出該矩陣的一個峰值元素，返回他的坐標原題鏈接一維二分搜索復(fù)雜度時間空間思路最直觀的方法是遍歷整個矩陣，但這要的時間。 Find Peak Element I A peak element is an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], fi...

    leiyi 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<