[Leetcode] Sort List

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

Similar to Merge sort, http://en.wikipedia.org/wiki/Merge_sort

1. Find the middle of the list and divide it into two part, the second one begin from middle
2. Recursively divide the two part until NULL or only one element in the list
3. Do the merge

Special test case: 2->1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
 //merge the two lists
    ListNode* mergeList(ListNode* head1, ListNode* head2)
    {
        ListNode* dummyHead = new ListNode(0);
        ListNode* curr = dummyHead;
        while(head1!=NULL && head2!=NULL)
        {
            if (head1->val < head2->val)
            {
                curr->next = head1;
                curr = curr->next;
                head1=head1->next;
            }
            else
            {
                curr->next = head2;
                curr = curr->next;
                head2=head2->next;
            }
        }
        
        while(head1!=NULL)
        {
            curr->next = head1;
            curr = curr->next;
            head1 = head1->next;
        }
        
        while(head2!=NULL)
        {
            curr->next = head2;
            curr = curr->next;
            head2 = head2->next;
        }
        
        ListNode* newHead = dummyHead->next;
        delete dummyHead;
        return newHead;
        
    }

    ListNode *sortList(ListNode *head) {
        if (head == NULL || head->next == NULL)
            return head;
        
        //divide the list into 2 part    
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* prev = NULL;
        //note: the second part should begin from slow rather than slow->next
        while(fast != NULL && fast->next != NULL)
        {
            prev = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        
        ListNode* head2 = slow;
        prev->next = NULL;
        
        ListNode * h1 = sortList(head);
        ListNode * h2 = sortList(head2);
        
        return mergeList(h1, h2);
        
    }
};