## 23. Merge k Sorted Lists (C++ Implementation Here)

Merge_k_sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

``````Input:

[1->4->5, 1->3->4,2->6]

Output:
1->1->2->3->4->4->5->6
``````

Thoughts:

1. With minheap:
2. While heap is not empty, pull the least element o out, then if the next element of the o is not null, add it to the heap.
2. Iterative merging:

Code: Priority Queue T:O(NlogN) Space: O(N)

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length ==0) return null;

PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.length, (n1, n2)-> n1.val - n2.val);
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
for(ListNode node : lists){
if (node != null)
}
while(!queue.isEmpty()){
cur = cur.next;

if(cur.next != null){   // put successor in the queue
}
}

return dummy.next;

}
}
``````

Code: Iterative Merging T:(NlogN) Space: O(1)

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists ==null || lists.length ==0) return null;
final int n = lists.length;
for (int b = 1; b < n; b<<=1){
for(int low = 0; low + b < n; low+= b<<1){
lists[low]=mergeTwoLists(lists[low], lists[low + b]);
}
}

return lists[0];
}

private ListNode mergeTwoLists(ListNode l1, ListNode l2){
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else{
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}

}
}
``````