[LeetCode] 148. Sort List

zhoutao 發布于2019-08-19 11:17 / 3539人閱讀

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

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/77357.html

leetcode148. Sort List

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

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

摘要：有效三角形的個數雙指針最暴力的方法應該是三重循環枚舉三個數字?？偨Y本題和三數之和很像，都是三個數加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸，所以空間復雜度為 ...

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

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

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

摘要：題目分析一看到問題，而且時間復雜度要求又是，很自然地就會想到數組時，如下這道題要求是，所以在上面的基礎上還要進行一些額外操作找到的中點，使用快慢指針法。需要注意的是，找到中點后要把鏈表分成兩段，即兩個鏈表。這部分代碼應該近似于這道題的答案。 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

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

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