ETH官方钱包

前往
大廳
主題

LeetCode - 148. Sort List 解題心得

Not In My Back Yard | 2022-10-05 12:00:04 | 巴幣 0 | 人氣 736

題目連結:


題目意譯:
給定一個連結串列(Linked List)的開頭節點 head,將其按升序排序後回傳該串列。

限制:
串列中的節點數量位於範圍 [0, 5 × 10 ^ 4] 中。
-10 ^ 5 ≦ Node.val ≦ 10 ^ 5

進階:你可以在 O(n log n) 時間內並使用 O(1) 記憶體(則常數空間)來排序連結串列嗎?



範例測資:
範例 1:
輸入: head = [4,2,1,3]
輸出: [1,2,3,4]

範例 2:
輸入: head = [-1,5,3,4,0]
輸出: [-1,0,3,4,5]

範例 3:
輸入: head = []
輸出: []


解題思維:
這題一樣我們可以先用一個「假節點」 dummy 來作為假的開頭,這樣合併後的串列可以直接接在 dummy 作為開頭的這個串列之尾端(這樣就不用考慮當前合併後的結果為空串列,所以沒有「尾端」之情況)。

接著我們可以仿照一般陣列時使用的合併排序法(Merge Sort,參見維基頁面),也就是利用這題的結果來找到串列的中間並將串列分為左右兩部分。接著遞迴各自排序左側和右側,最後按照正常流程合併成單一一個已排序之串列即可(如這題)。

而其時間複雜度同樣也是 O(n log n),不過上述這個遞迴的作法實際上空間複雜度是 O(log n)(因為遞迴深度會到 O(log n) 層)。但是改成迭代版本的即可降為 O(1),這部分就交給讀者實作(範例程式碼為遞迴版本)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作