Heeeelp~~~ Time Limit Exceeded

• ``````/**
* 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?

• 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;
}
}
if(pqueue.size() ==0)
return null;

while(pqueue.size()>1){
QueueListNode queueNode1 = pqueue.remove();
QueueListNode queueNode2 = pqueue.remove();
}
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);
}

```

}
'''``````

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