Leetcode -- Sort List

Seems the easiest way is to use merge sort

 /**  
  * 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) {  
     if(head == NULL || head->next == NULL) {  
       return head;  
     }  
     ListNode * slower = head;  
     ListNode * faster = head->next;  
     while(faster != NULL && faster->next != NULL) {  
       slower = slower->next;  
       faster = faster->next;  
       faster = faster->next;  
     }  
     ListNode * temp = slower->next;  
     slower->next = NULL;  
     ListNode * left = sortList(head);  
     ListNode * right = sortList(temp);  
     return mergeList(left, right);  
   }  
   ListNode * mergeList(ListNode * head1, ListNode * head2) {  
     ListNode * dummy = new ListNode(-1);  
     ListNode * p = dummy;  
     while(head1 != NULL || head2 != NULL) {  
       if(head1 != NULL && head2 != NULL) {  
         if(head1->val < head2->val) {  
           p->next = head1;  
           head1 = head1->next;  
         } else {  
           p->next = head2;  
           head2 = head2->next;  
         }  
         p = p->next;  
       }   
       if(head1 != NULL && head2 == NULL) {  
         p->next = head1;  
         break;  
       }  
       if(head2 != NULL && head1 == NULL) {  
         p->next = head2;  
         break;  
       }  
     }  
     return dummy->next;  
   }  
 };