## # 23. Merge k Sorted Lists

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
``````

### # Solution

Approach 1: use a priority queue to keep the current heads -- `O(N logk)`.

Approach 2: merge pairs of lists until there's 1 big list left -- `O(N logk)`.

### # Code (Python)

Approach 1:

``````    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
# random.random() just to avoid comparing ListNodes
heapq.heapify(heap)

while heap:
val, id, node = heapq.heappop(heap)
current.next = node
current = current.next
if node.next:
heapq.heappush(heap, (node.next.val, random.random(), node.next))

current.next = None
``````

Approach 2:

``````    def mergeKLists(self, lists):
if not lists:
return None
lists = collections.deque(lists)
while len(lists) > 1:
lists.append(self.merge2Lists(lists.popleft(), lists.popleft()))
return lists[0]

def merge2Lists(self, l1, l2):
dummy = ListNode(0)
current = dummy
while l1 and l2:
if l1.val <= l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
if l1:
current.next = l1
else:
current.next = l2
return dummy.next
``````

### # Code (C++)

Approach 1:

``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
// Compare one by one.
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
int n = lists.size();
vector<ListNode*> p(n, NULL);
for (int i = 0; i < n; ++i)
{
if (lists[i])
p[i] = lists[i];
}
while (true)
{
int minIdx = -1;
for (int i = 0; i < lists.size(); ++i)
{
if (p[i] && (minIdx < 0 || p[minIdx]->val > p[i]->val))
minIdx = i;
}
if (minIdx < 0)
break;
d->next = p[minIdx];
d = d->next;
p[minIdx] = p[minIdx]->next;
}
}
};

// Minimum heap.
class Solution {
private:
struct cmp {
bool operator() (ListNode *a, ListNode *b) {
return a->val > b->val;
}
};
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
int n = lists.size();
priority_queue<ListNode*, vector<ListNode*>, cmp> q;
for (int i = 0; i < n; ++i)
{
if (lists[i])
q.push(lists[i]);
}
while (!q.empty())
{
d->next = q.top();
d = d->next;
q.pop();
if (d->next)
q.push(d->next);
}
}
};
``````

Approach 2:

``````// Merge with divide and conquer.
class Solution {
private:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummyNode(0);
ListNode *d = &dummyNode;
while (l1 || l2)
{
if (l1 == NULL || l2 && l2->val <= l1->val)
{
d->next = l2;
l2 = l2->next;
}
else
{
d->next = l1;
l1 = l1->next;
}
d = d->next;
}
return dummyNode.next;
}
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
int n = lists.size();
if (n == 0)
return NULL;
for (int interval = 1; interval < n; interval *= 2)
{
for (int i = 0; i < n && i + interval < n; i += interval * 2)
{
lists[i] = mergeTwoLists(lists[i], lists[i+interval]);
}
}
return lists[0];
}
};
``````