Very modular Java O(1) space solution


  • 0
    L

    mergeByK takes two chunks and merges them with the merge function. In the merge function, h, h2 and h3 stand for the head of chunk 1, chunk 2 and the rest.

    public class Solution {
        public ListNode sortList(ListNode head) {
            int k=1;
            ListNode dummy = new ListNode(0);
            dummy.next=head;
            int round;
            do {
                round=0;
                ListNode prev = dummy;
                do {
                    prev = mergeByK(prev, prev.next, k);
                    round ++;
                } while (prev.next!=null);
                k*=2;
            } while (round>1);
            return dummy.next;
        }
        
        ListNode mergeByK(ListNode prev, ListNode h, int k) {
            ListNode h2 = h; int count = k;
            while (h2!=null && count>0) {
                h2=h2.next; count--;
            }
            ListNode h3=h2;count=k;
            while (h3!=null && count>0) {
                h3=h3.next; count--;
            }
            ListNode[] ret = merge(h, h2, h3);
            prev.next = ret[0];
            return ret[1];
        }
        
        ListNode[] merge(ListNode h, ListNode h2, ListNode h3) {
            ListNode dummy=new ListNode(0);
            ListNode prev = dummy;
            ListNode h2c = h2;
            while (h!=h2c || h2!=h3) {
    			if (h != h2c && (h2 == null || h2 == h3 || h.val < h2.val)) {
                    prev.next = h; h=h.next;
                } else {
                    prev.next = h2; h2=h2.next;
                }
                prev = prev.next;
            }
            prev.next = h3;
            return new ListNode[]{dummy.next, prev};
        }
    }

  • 0
    V

    Did you get AC with this code?

    In merge function, you always return null as ret[0].


  • 0
    L

    Yes, the code gets AC. dummy is used as a hook to get the head of merged list, so ret[0] is not necessarily null.


  • 0
    V

    you're right, you set the dummy.next via prev.next (and before prev = dummy)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.