148. Sort List

anquan 發布于2019-08-14 17:56 / 1273人閱讀

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

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

題目分析

一看到sort問題，而且時間復雜度要求又是O(n log n)，很自然地就會想到Merge sort. Merge sort數組時，pseudo code如下：

func mergesort( var a as array )
    if ( n == 1 ) return a

    var l1 as array = a[0] ... a[n/2]
    var l2 as array = a[n/2+1] ... a[n]

    l1 = mergesort( l1 )
    l2 = mergesort( l2 )

    return merge( l1, l2 )
end func

func merge( var a as array, var b as array )
    var c as array

    while ( a and b have elements )
         if ( a[0] > b[0] )
              add b[0] to the end of c
              remove b[0] from b
         else
              add a[0] to the end of c
              remove a[0] from a
    while ( a has elements )
         add a[0] to the end of c
         remove a[0] from a
    while ( b has elements )
         add b[0] to the end of c
         remove b[0] from b
    return c
end func
(Reference: http://www.algorithmist.com/i... )

這道題要求是sort linked list，所以在上面pseudo code的基礎上還要進行一些額外操作：

找到List的中點，使用快慢指針法。

ListNode slow = head;
ListNode fast = head;

while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}

需要注意的是，找到中點后要把鏈表分成兩段，即: slow.next = null;

Merge兩個鏈表。這部分代碼應該近似于merge 2 sorted lists這道題的答案。

代碼

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // find the mid point of the linked list
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode head2 = slow.next;
        slow.next = null;
        
        // if there"s only 1 element in the list, continue splitting
        ListNode list1 = null;
        ListNode list2 = null;
        if (head != head2) {
            list1 = sortList(head);
            list2 = sortList(head2);
        }
        
        // merge 2 lists
        return mergeList(list1, list2);
        
    }
    
    // merge 2 lists. reference: Merge 2 Linked List
    public ListNode mergeList(ListNode head1, ListNode head2) {
        if (head1 == null) {
            return head2;
        }
        
        if (head2 == null) {
            return head1;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val <= head2.val) {
                p.next = head1;
                p = p.next;
                head1 = head1.next;
            } else {
                p.next = head2;
                p = p.next;
                head2 = head2.next;
            }
        }
        
        if (head1 != null) {
            p.next = head1;
        }
        if (head2 != null) {
            p.next = head2;
        }
        
        return dummy.next;
    }
}

復雜度分析

時間復雜度 O(n log n)
空間復雜度 O(1)

云服務器 GPU云服務器 sort() sort sort()方法 sort方法

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

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

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
[LeetCode] 148. Sort List

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 S...

zhoutao 2019-08-19 11:17 評論0 收藏0
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】

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

Clect 2021-11-15 11:38 評論0 收藏0
MongoDB指南---16、聚合

摘要：將返回結果限制為前個。所以，聚合的結果必須要限制在以內支持的最大響應消息大小。包含字段和排除字段的規則與常規查詢中的語法一致。改變字符大小寫的操作，只保證對羅馬字符有效。只對羅馬字符組成的字符串有效。上一篇文章：MongoDB指南---15、特殊的索引和集合：地理空間索引、使用GridFS存儲文件下一篇文章：MongoDB指南---17、MapReduce 如果你有數據存儲在Mon...

Keagan 2019-06-26 18:06 評論0 收藏0