# 148 - Sort List

解法一 - 存到 array sort，再建立 list

這個解法不符合題目要求，不過還是先記一下實作：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head) return head;

        vector<int> nums;

        while(head){
            nums.push_back(head->val);
            head = head->next;
        }

        sort(nums.begin(), nums.end());

        ListNode* newHead = new ListNode(0);
        ListNode* cur = newHead;
        for(auto n:nums) {
            ListNode* node = new ListNode(n);
            cur->next = node;
            cur = cur->next;
        }

        return newHead->next;
    }
};

解法二 - Bottom-up merge sort

這個解法是參考這篇 discussion - https://leetcode.com/problems/sort-list/discuss/46712/Bottom-to-up(not-recurring)-with-o(1)-space-complextity-and-o(nlgn)-time-complextity。

如果要了解這個作法，需要去看一下 bottom-up merge sort。

解法三 - Divide and Conquer

解法三用到 recursion，所以空間複雜度其實是 O(logn)，不過還是記一下。

https://leetcode.com/problems/sort-list/discuss/46714/Java-merge-sort-solution