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) {
values.add(node.val);
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
andans
.
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 oflists
. 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 $$k1$$ 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 K1
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 oflists
. $$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 oflists
. 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
.