Convert Hard to Easy, Using Merge Sort, Not Using PiorityQueue


  • 0
    W

    If merge two List, it is easy, runing O(m+n). So we need to change hard to easy. Divid k to 2, and than conker ( merge), running time is O(knlgn), and no more memory.
    Here is my code.

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if(lists == null || lists.length == 0) return null;
            int last = lists.length-1;
    
            // repeat until only one list is left
            while (last != 0) {
                int i = 0, j = last;
                // (i, j) forms a pair
                while (i < j) {
                    // merge List i with List j and store
                    // merged list in List i
                    lists[i] = mergeTwoLists(lists[i], lists[j]);
                    // consider next pair
                    i++; j--;
                    // If all pairs are merged, update last
                    if (i >= j) last = j;
                }
            }
    
            return lists[0];
        }
        
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode dummy = new ListNode(0);
            ListNode p = dummy;
            while(l1 != null && l2 != null) {
                if(l1.val <= l2.val) {
                    p.next = l1;
                    p = l1;
                    l1 = l1.next;
                } else {
                    p.next = l2;
                    p = l2;
                    l2 = l2.next;
                }
            }
            
            if(l1 != null) p.next = l1;
            if(l2 != null) p.next = l2;  
            return dummy.next;
        }
    }

Log in to reply
 

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