Share my Java divide & conquer solution


  • 0
    P
    public ListNode mergeKLists(ListNode[] lists) {
            return divideC(lists, 0, lists.length);
        }
        
        private ListNode join(ListNode l1, ListNode l2) {
            if (l1 == null) {
                return l2;
            }
            if (l2 == null) {
                return l1;
            }
            ListNode c1 = l1;
            ListNode c2 = l2;
            ListNode res = new ListNode(-1);
            ListNode trace = res;
            while (c1 != null && c2 != null) {
                if (c1.val > c2.val) {
                    trace.next = c2;
                    c2 = c2.next;
                } else {
                    trace.next = c1;
                    c1 = c1.next;
                }
                trace = trace.next;
            }
            if (c1 != null) {
                trace.next = c1;
            }
            if (c2 != null) {
                trace.next = c2;
            }
            return res.next;
        }
        
        private ListNode divideC(ListNode[] list, int lo, int hi) {
            if(hi == lo) {
                return null;
            }
            if (hi - lo == 1) {
                return list[lo];
            } 
            if (hi - lo == 2) {
                return join(list[lo], list[lo + 1]);
            }
            int mid = (lo + hi) / 2;
            ListNode left = divideC(list, lo, mid);
            ListNode right = divideC(list, mid, hi);
            return join(left, right);
        }
    

Log in to reply
 

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