Java Recursive Solution ( Not Using PriorityQueue)


  • 0

    I've run both my solution and those solution using PriorityQueue multiple time. Their running time does not differ much and primarily ranges from 350ms to 380ms. I calculate the big-O of my solution to be O(nk) while n is the length of each sorted array assume they have equal length while k is the # of array. The PQ solution is claimed to be O(nlogk), so why isn't there a bigger differences?

    public class Solution {
        // what if some element is null
        public ListNode mergeKLists(ListNode[] lists) {
            int len = lists.length;
            if ( len == 0 ) {
                return null;
            } else if ( len == 1) {
                return lists[0];
            } else {
                ListNode[] newLists = new ListNode[(len+1)/2];
                for ( int i = 0; i < newLists.length; i++ ) {
                    int left = i, right = len-1-i;
                    if ( left == right ) {
                        newLists[i] = lists[i];    
                    } else {
                        newLists[i] = mergeTwoLists(lists[left], lists[right]);
                    }
                }
                return mergeKLists(newLists);
            }
        }
        
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            
            if ( list1 == null && list2 == null ) { return null;  }
            if ( list1 == null && list2 != null ) { return list2; }
            if ( list1 != null && list2 == null ) { return list1; }
            
            ListNode dummyHead = new ListNode(0);
            ListNode p1 = list1, p2 = list2, p3 = dummyHead;
            
            while ( p1 != null && p2 != null ) {
                if ( p1.val <= p2.val ) {
                    p3.next = p1; p1 = p1.next;
                } else {
                    p3.next = p2; p2 = p2.next;
                }
                p3 = p3.next;
            }
            p3.next = mergeTwoLists(p1, p2);
            
            return dummyHead.next;
        }
    }

  • 0
    F

    ListNode[] newLists = new ListNode[(len+1)/2];
    can you explain why the newLists array's length should be (len+1)/2 ?


  • 0

    For example, if the input array has four sorted linked list, the method will merge the 1st and 2nd linked list, and then merge 3rd and 4th linked list, so the output array has 2 sorted linked list; if the input array has five sorted linked list, the method will merge the 1st and 2nd linked list, and then merge 3rd and 4th linked list, so the output array has 3 sorted linked list with the 5th linked list unchanged.


  • 0

    FYI, this method is slower than the one that use PriorityQueue. Even though these two methods have the same complexity, PriorityQueue has fewer comparison operations.


  • 0
    F

    thank you very much, got it


  • 0
    F

    I am not sure if using PriorityQueue would be regarded as not programmatically coding this problem.


Log in to reply
 

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