/**
 * 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) 
    {
        ListNode* left;
        ListNode* right;
        quicksort(head,left,right);
        return left;
    }
    
    void quicksort(ListNode* head,ListNode*& left,ListNode*& right)
    {
        if(head==NULL)
        {
            left=NULL;right=NULL;
            return;
        }
        if(head->next==NULL)
        {
            left=head;
            right=head;
            return;
        }
        
        ListNode* headsmall=NULL;
        ListNode* smallp;
        
        ListNode* pre=head;
        ListNode* p=head->next;
        int val=head->val;
        
        bool issame=true;
        while(p!=NULL)
        {
            while(p!=NULL)
            {
                if(p->val!=val) issame=false;
                if(p->val<val) break;
                pre=p;
                p=p->next;
            }
            if(p!=NULL)
            {
                pre->next=p->next;
                if(headsmall==NULL) 
                {
                    headsmall=p;
                }
                else
                {
                    smallp->next=p;
                }
                smallp=p;
                p=p->next;
                smallp->next=NULL;
            }
        }
        //all the same
        if(issame && headsmall==NULL)
        {
            left=head;
            right=pre;
            return;
        }
        
        ListNode* headbig=head->next;
        head->next=NULL;
        
        ListNode* bigleft;
        ListNode* bigright;
        ListNode* smallleft;
        ListNode* smallright;
        
        if(headsmall!=NULL && headbig!=NULL)
        {
            quicksort(headbig,bigleft,bigright);
            quicksort(headsmall,smallleft,smallright);
            smallright->next=head;
            head->next=bigleft;
            left=smallleft;
            right=bigright;
        }
        else if(headsmall==NULL)
        {
            quicksort(headbig,bigleft,bigright);
            head->next=bigleft;
            left=head;
            right=bigright;
        }
        else if(headbig==NULL)
        {
            quicksort(headsmall,smallleft,smallright);
            smallright->next=head;
            left=smallleft;
            right=head;
        }
    }
};