Heeeelp~~~ Time Limit Exceeded


  • 0
    C
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public class NodeCompartor implements Comparator<ListNode>{
            public int compare(ListNode o1, ListNode o2){
                //Null is the biggest
                if(o1==null) return 1;
                if(o1!=null&&o2==null) return -1;
                if(o1.val>o2.val) return 1;
                if(o1.val<o2.val) return -1;
                return 0;
            }
        }
        public ListNode mergeKLists(ListNode[] lists) {
            if(lists==null||lists.length==0) return null;
            if(lists.length==1) return lists[0];
            //initialize sorting the original lists.
            //As a result, the node with the smaller val is located in lower position.
            //Nodes with bigger val are located in higher positions.
            //Null nodes are located in the highest positions.
            Arrays.sort(lists,new NodeCompartor());
            if(lists[0]==null) return null;
            ListNode ret=null;
            ListNode curr=null;
            List<ListNode> list=Arrays.asList(lists);
            //After the initialization,my principle is: always pick the list.get(0).val.(Because the init above)
            //Ather picking, list.get(0)=list.get(0).next. And the sequence need to be rearranged again. But we need only care about list.get(0)
            do{
                //always pick the lists[0].val
                if(list.get(0)!=null){
                    if(ret==null){
                        ret=new ListNode(list.get(0).val);
                        curr=ret;
                    }else {
                        curr.next = new ListNode(list.get(0).val);
                        curr = curr.next;
                    }
                    list.set(0, list.get(0).next);
                }else{
                    break;
                }
                
                //Rearrange list.get(0) in the list
                ListNode tmp=list.get(0);
                int i=1;
                for(;i<list.size();i++){
                    if(list.get(i)!=null&&(tmp!=null&&list.get(i).val<tmp.val||tmp==null)){
                        list.set(i-1,list.get(i));
                    }else{
                        list.set(i-1,tmp);
                        break;
                    }
                }
                if(i==list.size()){
                    list.set(i-1,tmp);
                }
            }while(list.get(1)!=null);//until only one listnode left
            if(list.get(0)!=null)
                //append the only one listnode left
                curr.next=list.get(0);
            return ret;
        }
    }
    

    It tells me that " Time Limit Exceeded", but I dont how to reduce the time complexity...
    Could anyone help?


  • 0
    P

    Use priority queue to pick which two lists merge.

    class QueueListNode{
         public QueueListNode(ListNode listnode, int size){
             this.listNode = listnode;
             this.size = size;
         }
         
         ListNode listNode;
         int size;
     }
    
    public class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            
            if(lists == null || lists.length == 0)
                return null;
            
            if(lists.length ==1)
                return lists[0];
            
            PriorityQueue<QueueListNode> pqueue = new PriorityQueue<QueueListNode>(new Comparator<QueueListNode>(){
                public int compare(QueueListNode list1, QueueListNode list2){
                    return list1.size - list2.size;
                }
            });
            
            for(int i=0; i<lists.length; i++){
                ListNode list = lists[i];
                if(list ==null)
                    continue;
                ListNode temp = list;
                int size =0;
                while(temp!= null){
                    size++;
                    temp = temp.next;
                }
                pqueue.add(new QueueListNode(list,size));
            }
            if(pqueue.size() ==0)
                return null;
            
            while(pqueue.size()>1){
              QueueListNode queueNode1 = pqueue.remove();
              QueueListNode queueNode2 = pqueue.remove();
              pqueue.add(merge(queueNode1,queueNode2));
            }
            return pqueue.remove().listNode;
            
            
        }
        public QueueListNode merge(QueueListNode queueNode1, QueueListNode queueNode2){
            ListNode temp1 =queueNode1.listNode;
            ListNode temp2 =queueNode2.listNode;
            ListNode mergedNode;
            
            if(temp1.val <= temp2.val){
                mergedNode = temp1;
                temp1= temp1.next;
            }else{
                mergedNode = temp2;
                temp2= temp2.next;
            }
            ListNode temp3 = mergedNode;
            
            
            while(temp1!= null && temp2 != null){
                if(temp1.val <= temp2.val){
                    temp3.next = temp1;
                    temp1 = temp1.next;
                }else{
                    temp3.next = temp2;
                    temp2 = temp2.next;
                    
                }
                temp3 = temp3.next;
            }
            if(temp1!=null){
                temp3.next = temp1;
            }else{
                temp3.next = temp2;
            }
            return new QueueListNode(mergedNode, queueNode1.size + queueNode2.size);
        }
        
        
        ```
        
        
        
    }
    '''

Log in to reply
 

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