Sort List

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

http://www.lintcode.com/en/problem/sort-list/

Discussion

看到O(log n)，自然想到每次sort一半的list，最后再merge。这个思想之前已经多次碰到了。

Solution

We did merge tow sorted lists before.

class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: You should return the head of the sorted linked list,
                    using constant space complexity.
     */
    ListNode *sortList(ListNode *head) {
        // write your code here
        if(head == NULL || head->next == NULL) return head;
        ListNode *fast = head, *slow = head, *preSlow = head;
        while(fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            preSlow = slow;
            slow = slow->next;
        }
        preSlow->next = NULL;
        ListNode *list1 = sortList(head);
        ListNode *list2 = sortList(slow);
        return mergeSortedList(list1, list2);
    }
private:
    ListNode *mergeSortedList(ListNode *list1, ListNode *list2) {
        ListNode dummy(-1);
        ListNode *merged = &dummy;
        while(list1 && list2) {
            if(list1->val < list2->val) {
                merged->next = list1;
                list1 = list1->next;
            } else {
                merged->next = list2;
                list2 = list2->next;
            }
            merged = merged->next;
        }
        merged->next = list1 ? list1 : list2;
        return dummy.next;
    }
};