/*sort-list*/
/**************/
/*
Sort a linked list in O(n log n) time using constant space complexity.
*/
/*************/

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x):val(x){}
}

ListNode *sortList(ListNode *head)
{
    if(head==NULL || head->next==NULL) return head;
    ListNode *slow=head,*fast=head->next;
    while(fast && fast->next){
         slow=slow->next;
         fast=fast->next->next;
    }
    ListNode *l1=sortList(slow->next);
    slow->next=NULL;
    ListNode *l2= sortList(head);
    return merge(l1,l2);  
}

ListNode *merge(ListNode *l1,ListNode *l2)
{
    ListNode head(0);
    ListNode *p=&head;
    while(l1&&l2){
         if(l1->val<=l2->val){
             p->next=l1;
             l1=l1->next;
         }else{
             p->next=l2;
             l2=l2->next;
         }
         p=p->next;
     }
     if(l1) p->next=l1;
     if(l2) p->next=l2;
     return head.next;
}