從LeetCode學演算法 - 36 Merge Sort (1)

0148. Sort List (Medium)

Question

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

Example 1

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

Example 2

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

分析/解題

試以O(n log n)的時間複雜度來排序一個linked list。
這題其實還有設定一個constant space complexity的條件，
但要達成這個條件的話，要很仔細的使用迭代的方式來做merge sort才行，
這邊主要會講一般的遞迴解(也就是空間複雜度不會是O(1))，
若對迭代解有興趣，可以參考 theoneneo 或 ** sladkey**** 的解法。**

關於排序有很多不同的方式，
我們這邊先來講一個相當常見且經典的排序法：合併排序法(Merge Sort)

合併排序法的概念是先拆半再合併 ，一般在演算法中為了遞迴起見，
會直接把拆半的部分叫mergesort ，而合併的部分就稱為merge 。

什麼是拆半？就是每次將整組資料分成兩半，
一路拆分直到只剩下一個，這時候每一個單位而言均為排序好的狀態。
(廢話XD 就一個而已當然是排好的)

拆分完以後，要進行合併的動作。
合併就是指將同一層的兩組資料，按大小由小到大 置入。
我們可以參考範例的動畫，一開始由於拆到每組只剩下一個，
可以很輕易的比較誰大誰小，進而每次將較小的放入到合併的陣列中，
所以每一次合併 完以後，我們都可以得到一個**由小排到大的一組資料，
同時下一次我們依舊可以使用兩組各自由小排到大的資料，
使用two pointer的方式就可以依序將其合併。**最後合併回最開始那一層，我們就可以得到一個排序好的陣列了。

Merge Sort範例

最後排序完的結果

這樣子將目標先拆小以後再進行合併的手段，
我們通常稱之為分治法(divide-and-conquer) ，
也就是將大問題拆成小問題解決的一套思路。
由於一定要拆成每組只有單筆資料，每次拆分為一半，
故拆分的時候，會拆成logN層；又每次合併也都需要掃過每筆資料，
總時間複雜度必須再乘上N，所以最終的時間複雜度為O(NlogN) 。

當中每次合併都需求一個新的位置來作為承接它的狀態，
所以一般來說可使用O(N) 的空間來儲存。

總體而言，一個mergesort的演算法流程大致如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function mergesort(arr, l, r) {
    if r > l {
        m = (l+r)/2
        mergesort(arr, l, m)
        mergesort(arr, m+1, r)
        merge(arr, l, m, r)
    }
}
function merge(arr, l, m, r) {
    開一個新的陣列tmp，將arr的index l到index r的部分複製過去(包含r)
    i = l, j = m+1, cnt = 0
    比較tmp[i]和tmp[j]，將較小的複製到arr[l+cnt]並遞增cnt跟有被複製的i/j其一
    重複上一個步驟直到一方沒有可以比較的部分，將剩餘的數字全數依序放入arr中
}

回到我們的問題，
現在要排序的應該是LinkedList，和陣列的唯一差別是，
我們需要一些手段才能取到中間點，這裡同樣使用slow跟fast兩個pointer的方式，讓slow一次走一格，而fast一次走兩格，直到fast到底的時候(遇到NIL)就代表slow應該走到一半了，此時不要忘記將中間的slow的前一個節點prev跟slow進行斷開 ，prev的用途就是用來紀錄slow的前一個節點的。
(因為不是陣列，我們是依靠next是否為NIL 這點來判斷節點的分組)

接著在merge的部分，我們取用了一個n作為dummy node(也就是用來紀錄開頭用的節點)，接著使用iterator(ite)來進行檢查，同樣是檢查哪個比較小，
這時對於Linked List而言應該是將節點串接在後面 即可。(不要忘記串接了某一個以後，該節點也要往下走，相當於陣列中的i跟j其一要遞增。)

最後同樣，若有一方無法比較，則我們可以直接把剩下的節點接上去。
(ite.next = n1或ite.next = n2)
範例程式碼的部分這邊採用了leetcode使用者jeantimex的解法，
筆者加了一點註解，搭配前面文章的說明，
使用者應該可以較輕鬆地了解整個解題的思路和作法。

Java

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(NlogN), O(logN)
將一個串列不斷拆成二等份，直到剩下單一節點，
相當於在求N可以被二分拆幾次，乘上最終會有N個單節點再次合併，
故總體時間複雜度為O(NlogN)。)
(註:這只是很粗糙的說法，有興趣可以翻閱演算法書籍，會有較嚴謹的證明)
(對於每一次的拆分搜尋都需要用O(1)的記憶體來儲存這層的stack，
理想狀況下會有logN層，故平均空間複雜度為O(logN)，
最差的狀況則為O(N))

「還有一些常見的排序，你能說出它們的時間複雜度嗎？」
(selection/insertion/bubble等均為O(N²)，quick/merge均為O(NlogN)，
需留意quicksort的worst case是O(N²))

相似及延伸

1.0021. Merge Two Sorted Lists (Easy)

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~