Sort List

题目：

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

分析：

merge sort还是不怎么记得住，这题没有特别之处，主要是考察链表实现。

merge sort的伪代码应该是这样

// 1. separate into two halfs
// 2. call merge sort for each half
// 3. merge them
应该属于一个典型的divide and conquer的过程。

解法：

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* findMiddle(ListNode* head) {
        ListNode dummy(0);
        dummy.next = head;

        ListNode* slow = &dummy;
        ListNode* fast = &dummy;
        while (fast->next != NULL && fast->next->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }

    ListNode* merge(ListNode* head1, ListNode* head2) {
        if (head1 == NULL) {
            return head2;
        }
        if (head2 == NULL) {
            return head1;
        }

        ListNode dummy(-1);
        ListNode* curr = &dummy;

        while (head1 != NULL && head2 != NULL) {

            if (head1->val < head2->val) {
                curr->next = head1;
                head1 = head1->next;
            } else {
                curr->next = head2;
                head2 = head2->next;
            }
            curr = curr->next;
            curr->next = NULL;
        }

        if (head1 != NULL) {
            curr->next = head1;
        }

        if (head2 != NULL) {
            curr->next = head2;
        }

        return dummy.next;
    }

    ListNode *sortList(ListNode *head) {
        // write your code here
        if (head == NULL || head->next == NULL) {
            return head;
        }

        // separate in half 
        ListNode* mid = findMiddle(head);
        ListNode* newhead = mid->next;
        mid->next = NULL;

        // apply merge sort
        ListNode* head1 = sortList(head);
        ListNode* head2 = sortList(newhead);

        // merge two sorted list
        return merge(head1, head2);
    }
};