In-place solution Java beats 82%


  • 0
    C
    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            int size = lists.length;
            for (int i = 0; (int)Math.pow(2, i) < size; i++) {
                int k = (int)Math.pow(2, i);
                for (int j = 0; j < size; j+= 2*k) {
                    if (j+k < size) {
                        mergeLists(lists, j, j+k);
                    }
                }
            }
            return size > 0 ? lists[0] : null;
        }
        
        public void mergeLists(ListNode[] lists, int i, int j) {
            ListNode p1 = lists[i], p2 = lists[j];
            ListNode dummyhead = new ListNode(0), cur = dummyhead;
            while (p1 != null && p2 != null) {
                if (p1.val <= p2.val) {
                    cur.next = p1;
                    p1 = p1.next;
                } else {
                    cur.next = p2;
                    p2 = p2.next;
                }
                cur = cur.next;
            }
            if (p1 != null) {
                cur.next = p1;
            } else {
                cur.next = p2;
            }
            lists[i] = dummyhead.next;
            dummyhead = null;
        }
    }
    ``

Log in to reply
 

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