Sort List

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

Solution:
merge sort: nullify next pointer. 

// merge-sort. O(n log n) time and O(log n) space for stack recursion

public class Solution {
    // move along list
    ListNode cur = null;
    
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        // count the number of nodes    
        int len = 0;
        ListNode p = head;
        while(p != null){
            len++;
            p = p.next;
        }
        
        cur = head;
        return sort(len);
    }
    
    public ListNode sort(int len){
        if(len == 1){
            ListNode node = cur;
            cur = cur.next;
            // nullify original linkage
            node.next = null;
            return node;
        }
        ListNode l = sort(len / 2);
        ListNode r = sort(len - len / 2);
        return merge(l, r);
    }
    
    public ListNode merge(ListNode l, ListNode r){
        if(l == null) return r;
        if(r == null) return l;
        
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        
        // append listnode which has smaller val to tail
        // it will nullify original linkage automatically
        while(l != null && r != null){
            if(l.val < r.val){
                tail.next = l;
                tail = l;
                l = l.next;
            }   
            else{
                tail.next = r;
                tail = r;
                r = r.next;
            }
        }
        if(l == null) tail.next = r;
        else if(r == null) tail.next = l;
        
        return dummy.next;
    }
    
}