Sort List

 
ListNode *sortList(ListNode *head) {
        // Notice the second condition check, other wise, stack overflow.
        if (!head || !head->next) return head;
       
        ListNode *fast = head, *slow = head;
        while(fast->next && fast->next->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
       
        fast = slow->next;
        slow->next = NULL;
        return merge(sortList(head), sortList(fast));
    }
   
    ListNode *merge(ListNode *left, ListNode *right)
    {
        ListNode dummy(0);
        ListNode *p = &dummy;   
        while(left && right)
        {
            if (left->val < right->val) {
                p->next = left;
                left = left->next;
            }
            else {
                p->next = right;
                right = right->next;
            }
            p = p->next;
        }
       
        p->next = left? left : right;
        return dummy.next;
    }