# Solution by awice

• #### Approach #1: Brute Force [Accepted]

Intuition and Algorithm

Collect every value of every list and sort it, then create a new list with those sorted values.

Java

``````class Solution {
public ListNode mergeKLists(ListNode[] lists) {
List<Integer> values = new ArrayList();
for (ListNode node : lists){
while (node != null) {
node = node.next;
}
}

Collections.sort(values);
ListNode ans = new ListNode(0);
ListNode cur = ans;
for (int v : values){
cur.next = new ListNode(v);
cur = cur.next;
}
return ans.next;
}
}
``````

Python

``````class Solution(object):
def mergeKLists(self, lists):
values = []
for node in lists:
while node:
values.append(node.val)
node = node.next

values.sort()
ans = cur = ListNode(None)
for v in values:
cur.next = cur = ListNode(v)
return ans.next
``````

Complexity Analysis

• Time Complexity: \$\$O(V \log V)\$\$, where \$\$V\$\$ is the total number of values in all lists in `lists`. `values` will have length \$\$V\$\$ and take \$\$O(V \log V)\$\$ time to sort.

• Space Complexity: \$\$O(V)\$\$, the length of `values` and `ans`.

#### Approach #2: Sequential Merge [Time Limit Exceeded]

Intuition and Algorithm

Merge every list into our answer, one at a time.

Java

``````class Solution {
public ListNode merge(ListNode A, ListNode B) {
if (A == null) return B;
if (B == null) return A;
if (A.val < B.val) {
A.next = merge(A.next, B);
return A;
} else {
B.next = merge(A, B.next);
return B;
}
}
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
ListNode ans = lists[0];
for (int i = 1; i < lists.length; i++){
ans = merge(ans, lists[i]);
}
return ans;
}
}
``````

Python

``````class Solution(object):
def mergeKLists(self, lists):
def merge(A, B):
ans = cur = ListNode(None)
while A and B:
if A.val > B.val: A, B = B, A
cur.next = cur = ListNode(A.val)
A = A.next
cur.next = A or B
return ans.next

if not lists: return []
ans = reduce(merge, lists)
return ans
``````

Complexity Analysis

• Time Complexity: \$\$O(V * k)\$\$, where \$\$V\$\$ is the total number of values in all lists in `lists`, and \$\$k\$\$ is the length of `lists`. Every merge operation with lists of length \$\$A\$\$ and \$\$B\$\$ is \$\$O(A+B)\$\$. In the worst case, we might merge almost all \$\$V\$\$ of our elements \$\$k-1\$\$ times, for a total complexity of \$\$O(V * k)\$\$.

• Space Complexity: \$\$O(V)\$\$, the length of `ans`.

#### Approach #3: Divide And Conquer Merge [Accepted]

Intuition and Algorithm

Instead of merging the smallest lists together `K-1` times, merge the largest lists together \$\$O(\log K)\$\$ times.

To manage this task, we will let `mergeInterval(..., s, e)` be the result of merging the lists `lists[s], lists[s+1], ..., lists[e]` together. We will merge the lists in the left half of the interval, and the right half; then merge those two results together.

Java

``````class Solution {
public ListNode merge(ListNode A, ListNode B) {
// As in Approach #2
}
public ListNode mergeInterval(ListNode[] lists, int s, int e) {
if (s == e) return lists[s];
if (s > e) return null;
int m = (s + e) / 2;
ListNode left = mergeInterval(lists, s, m);
ListNode right = mergeInterval(lists, m+1, e);
return merge(left, right);
}
public ListNode mergeKLists(ListNode[] lists) {
return mergeInterval(lists, 0, lists.length - 1);
}
}
``````

Python

``````class Solution(object):
def mergeKLists(self, lists):
def merge(A, B):
# As in Approach #2

def merge_interval(s, e):
if s == e: return lists[s]
if s > e: return None
m = (s + e) // 2
left = merge_interval(s, m)
right = merge_interval(m+1, e)
return merge(left, right)

return merge_interval(0, len(lists) - 1)
``````

Complexity Analysis

• Time Complexity: \$\$O(V * \log k)\$\$, where \$\$V\$\$ is the total number of values in all lists in `lists`, and \$\$k\$\$ is the length of `lists`. \$\$O(\log k)\$\$ merges are made, and all \$\$V\$\$ values are merged that many times.

• Space Complexity: \$\$O(V)\$\$. Every value is stored at most one time.

#### Approach #4: Priority Queue [Accepted]

Intuition and Algorithm

When building our answer, the next element will be the minimum of all of our lists. A priority queue is an ideal data structure to manage repeated queries of the minimum of some changing collection.

We maintain `heap`, a priority queue of the head nodes of our lists. Then, the top of the priority queue is always the next value to be added to our answer, and if the next node of that list is nonempty, we'll add it to our `heap`.

Java

``````class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(lists.length,
Comparator.<ListNode> comparingInt(node -> node.val));

ListNode ans = new ListNode(0), cur = ans;
for (ListNode node : lists) {
if (node != null) heap.offer(node);
}
while (!heap.isEmpty()) {
cur.next = heap.poll();
cur = cur.next;
if (cur.next != null) heap.offer(cur.next);
}
return ans.next;
}
}
``````

Python

``````class Solution(object):
def mergeKLists(self, lists):
heap = [(A.val, A) for A in lists if A]
heapq.heapify(heap)

cur = ans = ListNode(None)
while heap:
val, node = heapq.heappop(heap)
cur.next = cur = ListNode(val)
node = node.next
if node:
heapq.heappush(heap, (node.val, node))

return ans.next
``````

Complexity Analysis

• Time Complexity: \$\$O(V * \log k)\$\$, where \$\$V\$\$ is the total number of values in all lists in `lists`, and \$\$k\$\$ is the length of `lists`. Every poll (pop) and offer (push) operation during one execution of the while block is \$\$O(\log k)\$\$, since the priority queue has size \$\$O(k)\$\$. We do \$\$O(V)\$\$ of these operations.

• Space Complexity: \$\$O(k)\$\$: we only used \$\$O(k)\$\$ additional space in storing `heap`.

• The number of lists is already called k by the problem, it's unnecessary and confusing to invent additional variable K. And multiplying the number of lists with the largest length is rather pessimistic and inaccurate. Why not use the total number of elements instead?

• @StefanPochmann I chose (case insensitive) `K` precisely because `k` was already defined in the problem, and I've always used capital letters in the complexity analysis portion and wanted to be consistent. I think this is a style choice, and after reading your comment I thought about it for a long time.

The other part of your comment, I chose N, K because I felt N, K was more straightforward than to justify steps involving V = the number of values, but in retrospect I was wrong here.

In total, I think you are right on both counts and I have edited this article to express it in terms of `V, k` instead.

• @awice Case insensitive variables? Barbaric. Were you brought up by Basic coders? :-P