Divide & Conquer, similar to merge sort, beats 99%


  • 0
    E
    public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null || lists.length == 0) return null;
            if (lists.length == 1) return lists[0];
            return divide(lists, 0, lists.length - 1);
        }
        //divide all the list into 1 to 1 group, merge them accordingly
        private ListNode divide(ListNode[] ls, int i, int j) {
            if (i == j) return ls[i];
            if (i < j) {
                int m = (i + j) / 2;
                ListNode left = divide(ls, i, m);
                ListNode right = divide(ls, m + 1, j);
                return merge(left, right);
            }
            return null;
        }
        
        private ListNode merge(ListNode l1, ListNode l2) {
            if (l1 == null) return l2;
            if (l2 == null) return l1;
            ListNode head = new ListNode(0);  //dummy node
            ListNode pre = head, post = null;
            while (l1 != null && l2 != null) {
                if (l1.val <= l2.val) {
                    pre.next = l1;
                    pre = l1;
                    l1 = l1.next;
                }
                else {
                    post = l2.next;                
                    pre.next = l2;
                    pre = l2;
                    l2.next = l1;
                    l2 = post;
                }
            }
            //deal with the reminder
            pre.next = l1 == null ? l2 : l1;
            return head.next;
        }
    

Log in to reply
 

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