Given the head of a linked list, return the list after sorting it in ascending order.
Example 1:
Input: head = [4,2,1,3] Output: [1,2,3,4]
Example 2:
Input: head = [-1,5,3,4,0] Output: [-1,0,3,4,5]
Example 3:
Input: head = [] Output: []
Constraints:
- The number of nodes in the list is in the range
[0, 5 * 104]. -105 <= Node.val <= 105
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
SOL：
這一題真的是很有難度的一題，我卡了超級久，還花一個禮拜補了 linked list才看得懂花花的講解。
花花酱 LeetCode 148. Sort List - 刷题找工作 EP211
因為時間複雜度要 O(n logn)，所以必須要用Merge Sort。
解法一：
Top-down (recursion)
Time complexity: O(nlogn)
Space complexity: O(logn)
讀懂了花花的影片，可以寫出大致的程式碼，但值得一提的是，一般而言，快慢指針都是從head開始，但這個解法fast必須從head.next開始，否則沒有辦法把前面的linked list斷開，會陷入無窮迴圈。
看了影片的留言，也有人為此感到困擾~
當fast跟slow都從head開始，找到的slow會剛好是中間的node，但slow=None無法把前一個node斷開，導致陷入無窮迴圈。
因此必須找到中間node的前一個node，這樣才有辦法斷開link。所以讓fast=head.next，fast一開始就比slow多走一步，那當fast走完，slow會是中間node的前一個。
有前一個只要加個next就可以找下一個，然後再把slow.next指到None就可以了。
參考了之前練習的 [LeetCode] 21. Merge Two Sorted Lists，再搭配sortList本身要recursive，就可以把兩個sort好的list merge起來了。
解法二：(還沒搞懂，待補)
bottom up
Time complexity: O(nlogn)
Space complexity: O(1)
烘焙 (2)