Good morning! Here's our prompt for today.
You're given an array of multiple sorted linked lists. Can you write a method that returns it transformed into a single sorted linked list?

Each linked list
can be represented as a series of nodes with the following definition:
1function Node(val) {
2 this.value = val;
3 this.next = null;
4}
Here's how it would be invoked:
1// Input
2const arr = [
3 2 -> 6 -> 9,
4 1 -> 2 -> 7,
5 2 -> 6 -> 10
6]
7
8mergeLists(arr);
9
10// Output
111 -> 2 -> 2 -> 2 -> 6 -> 6 -> 7 -> 9 -> 10
Constraints
- Each list can have up to
100000
nodes - The cumulative sum of all the nodes in the linked lists will be <=
100000
- The values in the nodes will be in the range
-1000000000
and1000000000
- Let
n
andk
be the length of a linked list and number of lists - Expected time complexity :
O(n*k*log k)
- Expected space complexity :
O(k)
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx
​
def merge_lists(arr):
# fill in
return arr[0]
​
​
# Node definition
class Node:
def __init__(self, val):
self.val = val
self.next = None
​
​
def create_nodes(head, nodes):
for val in nodes:
new_node = Node(val)
head.next = new_node
head = new_node
​
​
list1 = Node(3)
nodes1 = [4, 5, 6, 7, 8, 9, 10]
create_nodes(list1, nodes1)
​
list2 = Node(1)
nodes2 = [2, 3, 4, 5, 6, 7, 8]
create_nodes(list2, nodes2)
​
​
def list_to_str(head):
Here's a video of us explaining the solution.
To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.

We'll now take you through what you need to know.
How do I use this guide?
This is a more difficult problem than it may initially seem!
An obvious brute force solution is simply to:
- Traverse through every list
- Store all the node values in an array
- Sort the array. Unfortunately here, the time complexity is O(n log n) since there are
n
total nodes and sorting takesO(n log n)
time.
We can improve on the brute force approach by instead comparing node to node, and putting them in the right order as we're traversing. This becomes very similar to the Merged Sorted Linked Lists problem.

A better approach is to introduce a data structure. We need something that is built to process and order elements one by one in an efficient manner. What about a priority queue?
A priority queue is an abstract data type used to maintain a queue, with each element having a concept of a priority or order to be served.
Let's start by implementing one with a simple insert
method:
xxxxxxxxxx
class PriorityQueue {
constructor() {
this.first = null;
this.size = 0;
}
​
insert(val) {
// decide where in the queue it falls
const newNode = new Node(val);
// if there's no first node or this new node is higher priority, move it to first
if (!this.first || newNode.val < this.first.val) {
newNode.next = this.first;
this.first = newNode;
} else {
// if it's a lower priority on the queue by value
let currNode = this.first;
​
// keep iterating until we find a node whose value we are greater than
while (currNode.next && newNode.val > currNode.next.val) {
currNode = currNode.next;
}
newNode.next = currNode.next;
currNode.next = newNode;
}
}
}
Then, using it is a matter of running the linked lists through it:
xxxxxxxxxx
let pq = new PriorityQueue();
for (let list of arrOfLists) {
if (list) {
let currentNode = list;
pq.insert(currentNode.val);
​
// process the rest of the list
while (currentNode.next) {
pq.insert(currentNode.next.val);
currentNode = currentNode.next;
}
}
}
​
// returning this will return the head of the priority queue linked list result
return pq.first || [];
Don't forget to handle the case when the array is empty:
xxxxxxxxxx
if (!arrOfLists || arrOfLists.length === 0) {
return [];
}
Let's put it all together now.
One Pager Cheat Sheet
- You can merge multiple
sorted linked lists
into a single sorted linked list, with time complexity ofO(n*k*log k)
and space complexity ofO(k)
. - We can improve the brute force solution to sorting a list of linked lists by introducing a
Priority Queue
data structure, which allows us to efficiently process and order elements one by one inO(n log n)
time. - The process involves
running
thelinked lists
through the designated software to achieve the desired result. - Always check for an empty array before attempting any operations.
Putting it all together
is the key to achieving success.
This is our final solution.
To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.
xxxxxxxxxx
print("Nice job, 2/2 tests passed!")
def sorted_merge(a, b):
result = None
​
if a == None:
return b
elif b == None:
return a
​
if a.val <= b.val:
result = a
result.next = sorted_merge(a.next, b)
else:
result = b
result.next = sorted_merge(a, b.next)
​
return result
​
​
def merge_lists(arr):
last = len(arr) - 1
​
while last != 0:
(i, j) = (0, last)
​
while i < j:
arr[i] = sorted_merge(arr[i], arr[j])
​
i += 1
j -= 1
​
if i >= j:
last = j
Got more time? Let's keep going.
If you had any problems with this tutorial, check out the main forum thread here.