Leetcode 148: sort List

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

 这个题目要求对list排序，time complexity要是O（nlogn)，最熟悉的当然是归并排序，我们知道归并排序在array上是O（nlogn）的时间复杂度， 但是对于Linklist是不是也是nlogn的时间复杂度呢？？ 对一个linklist归并排序，首先O(n）的时间复杂度找中点， 然后sort 左边，sort右边，最后merge， 所以最后时间复杂度其实也是O（nlogn）， logn是层数， n是每层merge的次数。
merge sort的一般思路： 1. 找middle node, 分为left and right 两部分的link list 2. 递归sort left and right 3. 对sort 好的left and right进行merge.
class Solution {
private:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur->next = l1;
                cur = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                cur = l2;
                l2 = l2->next;
            }
        }
        if (l1) cur->next = l1;
        if (l2) cur->next = l2;
        return dummy->next;
    }
public:
    ListNode* sortList(ListNode* head) {
        //sanity check
        if (head == NULL || head->next == NULL) return head;
        //find middle node
        ListNode* slow = head;
        ListNode* fast = slow;
        while (fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* mid = slow;
        ListNode* right = mid->next;
        mid->next = NULL;
        ListNode* left = head;
        left = sortList(left);
        right = sortList(right);
        ListNode* rst = merge(left, right);
        return rst;
    }
};