# Leetcode 148. Sort List
[148. Sort List](https://leetcode.com/problems/sort-list/) (<font color=#FFB800>Medium</font> 58.0%)

<!--
(<font color=#00AF9B>Easy</font> 53.8%)
(<font color=#FFB800>Medium</font> 39.6%)
(<font color=#FF375F>Hard</font>)
-->

- 限制 :

<ul>
<li><code>The number of nodes in the list is in the range [0, 5 * 10^4].</code></li>
<li><code>-105 <= Node.val <= 10^5</code></li>
</ul>

- Solution - A
第一種解法是直接拿 vector 放值，再用 vector 去排序，排序完再依序放回去。無恥，但很有用。
- 時間複雜度: $O(nlogn)$
- 空間複雜度: $O(n)$

- 程式碼

    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            vector<int> ans;
            ListNode* temp = head;
            while (temp) {
                ans.push_back(temp->val);
                temp = temp->next;
            }
            sort(ans.begin(), ans.end());
            int i = 0;
            temp = head;
            while (temp) {
                temp->val = ans[i];
                temp = temp->next;
                i++;
            }
            return head;
        }
    };

- Solution - B
第二種寫法就是乖乖地使用 merge sort 去寫。再寫的時候有幾點要注意!!
- 注意事項:
1. 如果 linked-list 為空或只有一個元素，直接 return。
2. 找到中間節點：使用快慢指針法找到 linked-list 的中間節點。快指針一次走兩步，慢指針一次走一步，當快指針走到結束時，慢指針剛好在中間。
3. 拆分 linked-list ：將 linked-list 從中間節點處斷開，形成左右兩個子 linked-list 。(不拆開會把記憶體弄爆掉)
4. 遞迴排序：對左右兩個子 linked-list 遞迴地使用 sortList 函數進行排序。
5. 合併已排序 linked-list ：使用 merge 函數將已排序的左右子 linked-list 合併。
- 時間複雜度: $O(nlogn)$
- 空間複雜度: $O(logn)$

- 程式碼

    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            if (!head || !head->next)
                return head;

            ListNode* mid = getMiddle(head);
            ListNode* left = head;
            ListNode* right = mid->next;
            mid->next = nullptr;

            left = sortList(left);
            right = sortList(right);

            return merge(left, right);
        }
    private:
        ListNode* getMiddle(ListNode* head) {
            if (!head) {
                return head;
            }
            ListNode* slow = head;
            ListNode* fast = head->next;
            while (fast && fast->next)
            {
                slow = slow->next;
                fast = fast->next->next;
            }
            return slow;
        }
        ListNode* merge(ListNode* left, ListNode* right) {
            if (left == nullptr) return right;
            if (right == nullptr) return left;

            if (left->val < right->val) {
                left->next = merge(left->next, right);
                return left;
            }
            else {
                right->next = merge(left, right->next);
                return right;
            }
            return nullptr;
        }
    };