LeetCode: Sort List

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 typedef ListNode ln;


   ListNode *Merge(ln *a, ln *b)  
   {  
     if(!a && !b)return a;  
     if(!a)return b;  
     if(!b)return a;  
     ln *t1 = a, *t2 = b,*prev = NULL;  
     ln *head = a->val<=b->val?a:b;  
     while(t1 && t2)  
     {  
       if(t1->val <= t2->val)  
       {  
         prev = t1;  
         t1 = t1->next;  
       }  
       else  
       {  
         if(prev)  
         {  
           prev->next= t2;  
         }  
         ln *tmp = t2->next;  
         t2->next = t1;  
         prev = t2;  
         t2 = tmp;  
       }  
     }  
     if(!t1)prev->next = t2;  
     return head;  
   }
   

  
   ListNode *MergeSort(ListNode *head) {  
     if(!head || !head->next)return head;  
     ln *fast=head, *slow=head, *prev;  
     while(fast && fast->next)  
     {  
       fast = fast->next->next;  
       prev = slow;  
       slow = slow->next;  
     }  
     prev->next = NULL;  
     ln *first = head, *second = slow;  
     ln *x = MergeSort(first);  
     ln *y = MergeSort(second);  
     head = Merge(x,y);  
     return head;  
   }  
   ListNode *sortList(ListNode *head) {  
     return MergeSort(head);  
   }