divide and conquer clean code beats 93%


  • 0
    K
    public class Solution {
        // divide and conquer
        public ListNode mergeKLists(ListNode[] lists) {
            return divide(lists, 0, lists.length -1);
        }
        
        private ListNode divide(ListNode[] lists, int start, int end) { // need to be lists.length() -1?
            if (start > end) {
                return null;
            }
            if (start ==  end) {
                return lists[start];
            }
            int mid = start + (end-start) /2;
            ListNode first = divide(lists, start,mid); // no one use mid
            ListNode second = divide(lists, mid + 1, end);
            return conquer(first, second);
        }
        
        private ListNode conquer(ListNode list1, ListNode list2) {
            ListNode result = new ListNode(0); // dummy node --> no need to manage to be 
            ListNode runner = result;
            while (list1 != null && list2 != null) {
                if (list1.val <= list2.val) {
                    runner.next = list1;
                    list1 = list1.next;
                }else {
                    runner.next = list2;
                    list2 = list2.next;
                }
                runner = runner.next;
            }
            
            runner.next = list1 == null? list2 :list1;
            return result.next; // delete that dummy node
            
        }
    }
    

  • 0
    I

    @keweiJ What do you think complexity of your code is?
    I did almost the same and I thought the complexity was log(k) for divide, and n for conquer (actually 2n in the worst case) => overall is O(n * log(k))

    But this link claims that divide-and-conquer takes O(n * k * log(k)):
    http://www.geeksforgeeks.org/merge-k-sorted-linked-lists/

    I guess I'm missing something here..


  • 0
    A

    Nice solution,. i solved this problem same as u, if k = lists.size() then time complexety is
    O( log(k) * sum( lists[0].length + .. + lists[k-1].length ) ) ,. if u think n is number of all nodes. O(n * log(k)) is absolutely true,.


Log in to reply
 

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