Sort List (LeetCode)

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

Idea: I used merge sort. If the list is longer than 2, split it to two halves at length/2, then sort the two halves individually, finally merge. I implemented a version with an extra parameter length to indicate the current length of the list. Therefore we do not need to calculate the length when a new recursion is evolved. This will not reduce the time complexity in big O notation, but it will make the algorithm to run faster in reality.

Time: O(nlgn) Space: O(lgn) (Since we need a stack to store the pointers when we keep splitting the list to halves until the real sort begins when the list has less than 3 nodes.

Code:

 public class Solution {  
   public ListNode sortList(ListNode head) {  
     int len=getLength(head);  
     return mergeSort(head,len);  
   }  
   public ListNode mergeSort(ListNode head,int length)  
   {  
     if(length<=1)  
       return head;  
     if(length==2)  
     {  
       if(head.val<=head.next.val)  
         return head;  
       ListNode dummy=new ListNode(0);  
       dummy.next=head.next;  
       head.next=null;  
       dummy.next.next=head;  
       return dummy.next;  
     }  
     ListNode pre=head;  
     for(int i=0;i<length/2-1;i++)  
       pre=pre.next;  
     ListNode secondHead=pre.next;  
     pre.next=null;  
     return merge(mergeSort(head,length/2),mergeSort(secondHead,length-length/2));  
   }  
   public ListNode merge(ListNode head1,ListNode head2)  
   {  
     if(head1==null)  
       return head2;  
     if(head2==null)  
       return head1;  
     ListNode dummy=new ListNode(0);  
     ListNode cur=dummy;  
     while(head1!=null&&head2!=null)  
     {  
       int val1=head1.val;  
       int val2=head2.val;  
       if(val1<=val2)  
       {  
         cur.next=head1;  
         head1=head1.next;  
       }  
       else  
       {  
         cur.next=head2;  
         head2=head2.next;  
       }  
       cur=cur.next;  
     }  
     if(head1!=null)  
       cur.next=head1;  
     if(head2!=null)  
       cur.next=head2;  
     return dummy.next;  
   }  
   public int getLength(ListNode head)  
   {  
     int counter=0;  
     while(head!=null)  
     {  
       counter+=1;  
       head=head.next;  
     }  
     return counter;  
   }  
 }