/**
knakul853
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {

        // merge sort techniqueue

        if(!head || !head->next)return head;

        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* tail = slow;

        while( fast && fast->next )
        {
            tail = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        tail->next = NULL;

        ListNode* left = sortList(head);
        ListNode* right = sortList(slow);
        return merge(left, right);
    }

    ListNode* merge( ListNode* h1, ListNode* h2 )
    {
        ListNode* dummy = new ListNode(0);
        ListNode* ans = dummy;

        while( h1 && h2 )
        {
            if( h1->val < h2->val )
            {
                dummy->next = new ListNode(h1->val);
                h1 = h1->next;
                dummy = dummy->next;
            }
            else{
                 dummy->next = new ListNode(h2->val);
                h2 = h2->next;
                dummy = dummy->next;
            }
        }

        dummy->next = h1 ? h1 : h2;

        return ans->next;
    }

};