LeetCode 148: Sort List

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

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        // Adopt Bottom-up mergesort
        if (head==null || head.next==null)
            return head;
            
        int n = 0; // Length of list
        ListNode node = head;
        
        while (node != null)
        {
            n++;
            node = node.next;
        }
        
        ListNode helper = new ListNode(0);
        helper.next = head;
        
        // pre - pre node of merge list (list1 + list2)
        // next - next node of merge list (list1 + list2)
        ListNode pre, next, head1, head2, end1, end2;
        
        // sz - length of list1 or list2
        for (int sz = 1; sz < n; sz = sz+sz)
        {
            pre = helper;
            
            for (int lo = 0; lo < n-sz; lo += sz+sz)
            {
                head1 = pre.next;
                end1 = move(head1, sz-1);
                head2 = move(end1, 1);
                end2 = move(head2, sz-1);
                next = move(end2, 1);
                
                // Set next node of end node of list1 as null
                if (end1 != null)
                    end1.next = null;
                
                // Set next node of end node of list2 as null
                if (end2 != null)
                    end2.next = null;
                
                pre = mergeTwoLists(pre, head1, head2);
                
                // Set next 'pre' node as current 'next' node
                pre.next = next;
            }
        }

        return helper.next;
    }
    
    // Move pointer form 'node' by 'step' steps
    private ListNode move(ListNode node, int step)
    {
        while (node!=null && step>0)
        {
            node = node.next;
            step--;
        }
        
        return node;
    }
    
    // Merge two lists (Both length is 'len')
    // Return the last node as the pre node of next merge
    private ListNode mergeTwoLists(ListNode pre, ListNode l1, ListNode l2)
    {
        ListNode p1 = l1; // Point to l1
        ListNode p2 = l2; // Point to l2

        while (p1!=null || p2!=null)
        {
            if (p1 == null)
            {
                pre.next = p2;
                p2 = p2.next;
                pre = pre.next;
            }
            else if (p2 == null)
            {
                pre.next = p1;
                p1 = p1.next;
                pre = pre.next;
            }
            else if (p1.val < p2.val)
            {
                pre.next = p1;
                p1 = p1.next;
                pre = pre.next;
            }
            else
            {
                pre.next = p2;
                p2 = p2.next;
                pre = pre.next;
            }
        }
        
        return pre;
    }
}