O N(log N) Iterative merge in Java


  • 0
    J

    I'm noticing that some of these "hard" problems end up having stupid-simple solutions, and the trick is being able to see the solution. I don't know if that is going to be true for all of them, but so far, it has been the case for the ones I've tried.

    public class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            ListNode result = null;
            
            if ( lists.length > 0 ) {
                if ( lists.length > 1 ) {
                    int half = lists.length;
                    while ( half > 1 ) {
                        if ( half % 2 != 0 ) {
                            lists[0] = merge(lists[0], lists[--half]);
                        }
                
                        half = half/2;
                        for ( int n=0; n<half; n++ ) {
                            lists[n] = merge(lists[n], lists[half+n]);
                        }
                    }            
                }
                
                result = lists[0];
            }
            
            return result;
        }
    
        private ListNode merge(ListNode list1, ListNode list2) {
            ListNode result = null;
            ListNode last = null;
    
            while ( list1 != null && list2 != null ) {
                ListNode min;
                
                if ( list1.val <= list2.val ) {
                    min = list1;
                    list1 = list1.next;
                } else {
                    min = list2;
                    list2 = list2.next;
                }
                
                if ( last == null ) {
                    result = last = min;
                } else {
                    last.next = min;
                    last = last.next;
                }
            }
            
            if ( last != null ) {
                last.next = (list1 != null ? list1 : list2);
            } else {
                result = (list1 != null ? list1 : list2);
            }
            
            return result;
        }
    }

  • 0
    Y

    It is not O(logn)


  • 0
    J

    Well, thank you for noticing my typo. I suppose if you know what it isn't, you must know what it is.


Log in to reply
 

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