[LeetCode]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) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        int len = getLen(head);  
        return sortListUtil(head, len);  
    }  
private:  
    ListNode* sortListUtil(ListNode* head, int len)  
    {  
        if(len <= 1) return head;  
        ListNode* head1 = NULL;  
        ListNode* head2 = NULL;  
        int len1, len2;  
        divideList(head, len, head1, len1, head2, len2);  
        head1 = sortListUtil(head1, len1);  
        head2 = sortListUtil(head2, len2);  
        ListNode* newHead = mergeList(head1, head2);  
        return newHead;  
    }  
    int getLen(ListNode* head)  
    {  
        int len = 0;  
        while(head)  
        {  
            len++;  
            head = head->next;  
        }  
        return len;  
    }  
    void divideList(ListNode* head, int len, ListNode*& head1, int& len1, ListNode*& head2, int& len2)  
    {  
        int firstHalfLen = len/2;  
        head1 = head;  
        ListNode* pDivideNode = head1;  
        for(int k = 1; k < firstHalfLen; ++k)  
            pDivideNode = pDivideNode->





next;  
        if(pDivideNode != NULL)  
        {  
            head2 = pDivideNode->next;  
            pDivideNode->next = NULL;  
        }  
        else head2 = NULL;  
        len1 = firstHalfLen;  
        len2 = len-len1;  
    }  
    ListNode* mergeList(ListNode* head1, ListNode* head2)  
    {  
        ListNode dummy(-1);  
        ListNode* prev = &dummy;  
        while(head1 && head2)//all not null  
        {  
            if(head1->val < head2->val)  
            {  
                prev->next = head1;  
                head1 = head1->next;  
            }  
            else  
            {  
                prev->next = head2;  
                head2 = head2->next;  
            }  
            prev = prev->next;  
        }  
        //remained head1 is not null  
        if(head1) prev->next = head1;  
        //remained head2 is not null  
        if(head2) prev->next = head2;  
          
        return dummy.next;  
    }  
};