0148. Sort List - chasel2361/leetcode GitHub Wiki

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

這題要求將串鍊排序，這邊先使用 Merge Sort 來解，但此法的空間複雜度不為 O(1)，所以僅供參考。Merge Sort 法的概念在於將資料像二元搜尋樹一樣，先取中間值做為根，不停對半拆分直至剩下一個，再按照想要的條件合併資料，整體概念如下圖。

此處需要處理的資料為串鍊，取中間值較不方便，這裡採用的方法有點類似之前 Linked List Cycle 的狀況，一樣使用 slow 與 fast 兩種移動速度不同的指標來判斷中間值，差別在於上次為了確認串鍊的長度，停止的條件設定為 slow 與 fast 相同，此處只要移動速度比 slow 快一倍的 fast 走到盡頭就表示 slow 剛好走到一半的位置，這樣只要在使用一個指標來儲存 slow 的前一個串鍊就可以了。

合併時依序將兩個相鄰的資料一一對照，將較小的串鍊接入要回傳的變數中即可。

[1] 將串鍊斷開
[2] 遞迴拆分串鍊

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head
            
        pre, slow, fast = None, head, head
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next        
        pre.next = None  #[1]
        n1 = self.sortList(head)  #[2]
        n2 = self.sortList(slow)  #[2]
        return self.merge(n1, n2)   
            
    def merge(self, n1, n2):
        n = ListNode(0)
        itr = n
        while n1 and n2:
            if n1.val < n2.val:
                itr.next = n1
                n1 = n1.next
            else:
                itr.next = n2
                n2 = n2.next
            itr = itr.next
        if n1: itr.next = n1
        if n2: itr.next = n2        
        return n.next

由於每次拆分是對半分，會拆 log(N) 次，最後合併時會把所有資料掃過一遍，所以整體的時間複雜度為 O(Nlog(N))，空間複雜度為 O(N)

---

若要符合題目要求，也就是空間複雜度為 O(1) 的話便不能使用遞迴法，此時仍然可以使用 Merge Sort ，但必須倒過來做。把原本拆分資料的過程改為一次取 2 的指數個資料排序，直至僅取兩組資料為止，詳細作法如下。

[1] tail 作為 dummy 的指標，當 tail 被修改時，dummy 也會被修改
[2] bs 受到 bitwise operator 作用，每次都多進一位 (二進位)

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head        
        def getSize(head):
            count = 0
            while head:
                count += 1
                head = head.next
            return count
            
        def split(head, count):
            i = 1
            while i < count and head:
                head = head.next
                i += 1
            if not head: return None
            temp = head.next
            head.next = None
            return temp
            
        def merge(l, r, head):
            cur = head
            while (l and r):
                if l.val < r.val:
                    cur.next = l
                    l = l.next
                else:
                    cur.next = r
                    r = r.next
                cur = cur.next                
            cur.next = l or r
            while cur.next:
                cur = cur.next
            return cur
            
        size = getSize(head)
        bs = 1
        dummy = ListNode(0)
        dummy.next = head
        l, r, tail = None, None, None
            
        while bs < size:
            cur = dummy.next
            tail = dummy  #[1]
            while cur:
                l = cur
                r = split(l, bs)
                cur = split(r, bs)
                tail = merge(l, r, tail)
            bs <<= 1  #[2]
        return dummy.next

這個做法可以保持時間複雜度為 O(Nlog(N))，且空間複雜度下降至 O(1)，但實際上跑出來的速度似乎比前面的方法慢了一些。