O(N) mergesort solution

[vkaruri]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    int print = 0;
    public ListNode sortList(ListNode head) {
        ListNode p = head;
        int len = 0;
        while (p != null) {
            len++;
            p = p.next;
        }
        return sortListHelper(head, len);
    }
    
    private ListNode sortListHelper(ListNode head, int len) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode mid = getMid(head, len);
        ListNode leftList = sortListHelper(head, len / 2);
        ListNode rightList = sortListHelper(mid, len / 2);
        
        // merge here
        ListNode result = new ListNode(-1);
        ListNode p = result;
        ListNode p1 = leftList;
        ListNode p2 = rightList;
        while (p1 != null || p2 != null) {
            ListNode next = null;
            if (p1 == null) {
                next = p2;
                p2 = p2.next;
            } else if (p2 == null) {
                next = p1;
                p1 = p1.next;
            } else {
               if (p1.val < p2.val) {
                   next = p1;
                   p1 = p1.next;
               } else {
                   next = p2;
                   p2 = p2.next;
               }
            }
            
            p.next = next;
            p = p.next;
        }
        
        return result.next;
    }
    
    private ListNode getMid(ListNode head, int len) {
        ListNode p = head;
        int count = 1;
        while (count < (len / 2)) {
            p = p.next;
            count++;
        }
        
        ListNode p1 = p.next;
        p.next = null;
        return p1;
    }
}