Sort List

Question

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

Example 1:

Input: 4->2->1->3 Output: 1->2->3->4 Example 2:

Input: -1->5->3->4->0 Output: -1->0->3->4->5

Solution

For the list, we need to know the size of each merge part (len1, len2 in the code). The remaining code is the same as Merge Two Sorted List.

class Solution {
    public ListNode sortList(ListNode head) {
        // First, get the total length, so that we know how to assign the width
        int len = 0;
        ListNode curNode = head;
        while(curNode!=null) {
            curNode = curNode.next;
            len++;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        for(int w=1;w<len;w*=2) {
            // use curNode: 1) to keep track of the start point 2) connect the previous section with next section or NULL
            curNode = dummy; 

            for(int i=0;i<len-w;i+=2*w) {
                // head 1: i; head 2: i+w
                // each list length: 
                int len1 = Math.min(w,len-i);
                int len2 = Math.min(w,len-i-w);
                ListNode h1 = curNode.next;
                ListNode h2 = h1;

                //get start point of second head
                for(int k=0; k<len1; k++) h2 = h2.next;     
                ////////////////////////////////////////////////                
                // merge two sorted list with len1 and len2
                int cnt1 = 0, cnt2 = 0;                
                while(cnt1<len1 && cnt2<len2) {
                    if(h1.val<h2.val) {
                        curNode.next = h1;
                        h1 = h1.next;
                        cnt1++;
                    }else {
                        curNode.next = h2;
                        h2 = h2.next;
                        cnt2++;
                    }
                    curNode = curNode.next;
                }
                while(cnt1<len1) {
                    curNode.next = h1;
                    h1 = h1.next;
                    cnt1++;
                    curNode = curNode.next;
                }
                while(cnt2<len2) {
                    curNode.next = h2;
                    h2 = h2.next;
                    cnt2++;
                    curNode = curNode.next;
                }
                ///////////////////////////////////////////////////
                curNode.next = h2; // connect the end node with next section or null
            }

        }
        return dummy.next;

    }
}