class Solution {

public ListNode mergeKLists(ListNode[] lists) {

// merge odd and even untill one left

```
//time complexity is O(NlogN);space complecity is O(N)
if(lists==null||lists.length==0) return null;
List<ListNode> list= new ArrayList<ListNode>(Arrays.asList(lists));
while(list.size()>1){
ListNode l1=list.remove(0);
ListNode l2=list.remove(0);
ListNode merged= merge(l1,l2);
list.add(merged);
}
return list.remove(0);
}
ListNode merge(ListNode l1, ListNode l2){
ListNode h1=l1,h2=l2,dummy=new ListNode(1),cur=dummy;
while(h1!=null &&h2!=null){
if(h1.val<h2.val){
cur.next=h1;
cur=h1;
h1=h1.next;
}else{
cur.next=h2;
cur=h2;
h2=h2.next;
}
}
if(h1==null) cur.next=h2;
if(h2==null) cur.next=h1;
return dummy.next;
}
```

}