[LeetCode] 148. Sort List

zhoutao 發(fā)布于2019-08-19 11:17 / 3598人閱讀

Problem

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Solution Merge Sort Space: O(logN) Time: O(NlogN)

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode slow = head, fast = head, split = head;
        while (fast != null && fast.next != null) {
            split = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        split.next = null;
        ListNode l1 = sortList(slow);
        ListNode l2 = sortList(head);
        head = merge(l1, l2);
        return head;
    }
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), head = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                head.next = l1;
                l1 = l1.next;
            } else {
                head.next = l2;
                l2 = l2.next;
            }
            head = head.next;
        }
        if (l1 != null) head.next = l1;
        if (l2 != null) head.next = l2;
        return dummy.next;
    }
}

云服務(wù)器 GPU云服務(wù)器 LeetCode LeetCode_String leetcode_35_SearchIn sort()

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

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

相關(guān)文章

leetcode148. Sort List

摘要：題目要求用的時(shí)間復(fù)雜度和的空間復(fù)雜度檢索一個(gè)鏈表。那么問題就歸結(jié)為如何將鏈表分為大小相近的兩半以及如何將二者合并。之后再對折斷的鏈表分別進(jìn)行計(jì)算從而確保每一段內(nèi)的元素為有序的。題目要求 Sort a linked list in O(n log n) time using constant space complexity. 用O(n log n)的時(shí)間復(fù)雜度和O(1)的空間復(fù)雜度檢...

OpenDigg 2019-08-15 13:35 評論0 收藏0
LeetCode 精選TOP面試題【51 ~ 100】

摘要：有效三角形的個(gè)數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個(gè)數(shù)字。總結(jié)本題和三數(shù)之和很像，都是三個(gè)數(shù)加和為某一個(gè)值。所以我們可以使用歸并排序來解決這個(gè)問題。注意因?yàn)闅w并排序需要遞歸，所以空間復(fù)雜度為 ...

Clect 2021-11-15 11:38 評論0 收藏0
148. Sort List

摘要：題目解答對于中第二個(gè)最優(yōu)解的解釋根據(jù)時(shí)間復(fù)雜度的要求，很容易想到應(yīng)該用的方法來做，那么就有兩個(gè)步驟，分和法。題目：Sort a linked list in O(n log n) time using constant space complexity. 解答：(對于discuss中第二個(gè)最優(yōu)解的解釋）根據(jù)時(shí)間復(fù)雜度的要求，很容易想到應(yīng)該用merge sort的方法來做，那么就有兩個(gè)...

kun_jian 2019-08-14 14:09 評論0 收藏0
148. Sort List

摘要：題目分析一看到問題，而且時(shí)間復(fù)雜度要求又是，很自然地就會(huì)想到數(shù)組時(shí)，如下這道題要求是，所以在上面的基礎(chǔ)上還要進(jìn)行一些額外操作找到的中點(diǎn)，使用快慢指針法。需要注意的是，找到中點(diǎn)后要把鏈表分成兩段，即兩個(gè)鏈表。這部分代碼應(yīng)該近似于這道題的答案。 Sort a linked list in O(n log n) time using constant space complexity. 題...

anquan 2019-08-14 17:56 評論0 收藏0
[LeetCode/LintCode] Merge Intervals

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

gougoujiang 2019-08-14 15:16 評論0 收藏0