Why is TLE?? I just look at every list for each iteration.HELP!


  • 0
    B
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0)   return null;
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;
        dummy.next = lists[0]; int ind = -1;
        while(true){
            int count = 0;
            ind = -1;
            for(int i = 0; i < lists.length;i++){
                //find minimum one
                //put it onto lists[0], chage lists[0]
                //when all but one is not null, can not compare just appedn
                if(lists[i]!=null)  {count ++;
                if(count == 1) ind = i;}
            }
            if(count <= 1)  {break;}
            //find minimum one
            int min = Integer.MAX_VALUE, min_ind = -1;
            for(int i = 0; i < lists.length; i++){
                if(lists[i]!=null && lists[i].val < min){
                    min_ind = i;
                    min = lists[i].val;
                }
            }
            if(min_ind != 0){
                ListNode list_ind_next = lists[min_ind].next;
                pre.next = lists[min_ind];
                lists[min_ind].next = lists[0];
                lists[min_ind] = list_ind_next;
                pre = pre.next;
            }
            else{
                lists[0] = lists[0].next;
                pre = pre.next;
            }
        }
         if(ind!=-1&&ind!=0) pre.next = lists[ind];
         return dummy.next;
    }

  • 0
    J

    Everytime you insert a min element to dummy, you should do k times of compare,total n * k, so your algorithm is O(n * k) complexity.


Log in to reply
 

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