Sort List

    ListNode *sortList(ListNode *head) {
        if(!head||!head->next) return head;
        ListNode*fast,*slow;
        fast=slow=head;
        while(fast->next&&fast->next->next){
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode*head2=slow->next;
        slow->next=NULL;
        head=sortList(head);
        head2=sortList(head2);
        return merge(head,head2);
    }
//insert the nodes of l2 into l1
    ListNode*merge(ListNode*l1,ListNode*l2){
        ListNode dummy(0),*prev=&dummy;
        dummy.next=l1;
        while(l2&&prev->next){
            if(l2->val<prev->next->val){
                ListNode*ne=l2->next;
                l2->next=prev->next;
                prev->next=l2;
                l2=ne;
            }
            prev=prev->next;
        }
        if(prev->next==NULL)
            prev->next=l2;
        return dummy.next;
    }

//another flavor of merge function, from annikim
    ListNode*merge(ListNode*l1,ListNode*l2){
        ListNode dummy(0),*last=&dummy;
        while(l1&&l2){
            ListNode**min=l1->val<l2->val?&l1:&l2;
            last->next=*min;
            last=last->next;
            *min=(*min)->next;
        }
        if(l1)
            last->next=l1;
        if(l2)
            last->next=l2;
        return dummy.next;   
    }