A java optimal solution based on loser tree


  • 1
    L

    I used loser tree to solve this problem. The time complexity was O((n-1)*logk), and the extra space required by loser tree is int[k]. If you have any question about my algorithm, please let me know.

    By the way , I found a bun in the default algorithm that used in test cases. You can repeat it with the input "[[6,10,33,2147483647,2147483647],[-2147483648,-2147483648,10, 18,20,33,38],[-2147483648, 2,3,10,15, 55]]". The default algorithm return wrong result [6,10,33,2147483647,2147483647,-2147483648,2,3,10,15,55,-2147483648,-2147483648,10,18,20,33,38], but the correct result is [-2147483648,-2147483648,-2147483648,2,3,6,10,10,10,15,18,20,33,33,38,55,2147483647,2147483647].

     public class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            List<ListNode> newLists = new ArrayList<ListNode>();
            for(ListNode node : lists) {
                if (node != null) {
                    newLists.add(node);
                }
            }
            if(newLists.size() == 0) {
                return null;
            } 
            if (newLists.size() == 1) {
                return newLists.get(0);
            }
            ListNode head = new ListNode(0);
            int k = newLists.size();
            // 0 - winner, 1~k-1:loser, k+1: MIN_VALUE
            int[] a = new int[k];
            ListNode[] b = new ListNode[k+1];
            b[k] = new ListNode(Integer.MIN_VALUE);
            for (int i = 0; i< k; i++) {
                a[i] = k;
                b[i] = newLists.get(i);
            }
            
            // init loser tree
            for (int i = k-1; i >= 0; i--) {
                adjust(a, i, b);   
            }
            
            int finishedCount = 0;
            ListNode cur = head;
            while(finishedCount < k) {
                int winner = a[0];
                cur.next = b[winner];
                cur = cur.next;
                if (cur.next != null) {
                    b[winner] = cur.next;
                } else {
                    b[winner] = new ListNode(Integer.MAX_VALUE);
                    finishedCount ++;
                }
                adjust(a, winner, b);
            }
            
            return head.next;
        }
        
        private void adjust(int[] a, int winner, ListNode[] lists) {
            int curP = winner;
            int k = lists.length -1 ;
            for (int i = (k+winner)/2; i > 0; i = i/2) {
                // parent is winner, set curP to the loser node(a[i]), and set parent node(old a[i] value) to curP
                if(lists[a[i]].val <= lists[curP].val) {
                    int tmp = a[i];
                    a[i] = curP;
                    curP = tmp;
                }
            }
            a[0] = curP;
        }
    
    }
    

Log in to reply
 

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