 Join us and get access to thousands of tutorials and a community of expert Pythonistas.

# Hard Interview Question (Brute Force)

In this lesson, you’ll use what you learned in the previous sections to solve a hard real world interview question. Hard means something you might find in a more difficult technical phone screen or an onsite interview.

Here’s the question:

``````class Link:
def __init__(self, val, next=None):
self.val = val
self.next = next

def __str__(self):
if not self.next:

'''
Merge k sorted linked lists into one
... ]))
... ]))
'''
``````

In this first lesson, you’ll go through a brute force solution. The entire solution will be available at the end of the course. Try the problem yourself and then watch the video for the solution.

If you want to learn more about linked lists, check out Linked Lists in Python: An Introduction. belushkin

My solution before watching video:

``````import heapq

def __init__(self, val, next=None):
self.val = val
self.next = next

def __str__(self):
if not self.next:

"""
"""

v = res
v = v.next

return res
``````

I guess complexity would be: log(N) for priority queue and 2N for for list traversal. So it would be Nlog(N) James Uejio RP Team

@belushkin thank you for sharing! Yes that is the case where N is the number of elements (in my example I use k and n as different variables). James Uejio RP Team

Note for everyone, if you want to learn more about linked lists, here is a Wikipedia article Özgür Gündoğan

My solution taking the advantage of that `Link` class does not contain any special information. If link class contains any special information, this is not useful.

``````def merge_k_linked_lists(linked_lists):
all_values=[]
all_values=sorted(all_values,reverse=True)

for val in all_values:
else:
`````` James Uejio RP Team

Nice solution Ozgur! linus-g

Here is my solution. It finds the linked list that has the current link with the smallest value, and then adds that link on to the end of the new list and removes it from its original list. This should make efficient use of the fact that all the linked lists are themselves sorted.

``````def merge_k_linked_lists(linked_lists):

while len(linked_lists) > 0:

# Find the smallest link by value in of all the links currently in linked_lists

if first_link_in_new_list is None:
# If this is the first iteration, set up new linked list
else:

# Update the linked list that had the smallest value,
# remove if there are no more values
else:

`````` Elise Ratcliffe

I’m trying to understand your solution, but there’s a part I’m really struggling with. I’ve commented the code to explain what I’m not understanding. I’ve had a look at the resources provided, but I’m still not getting what’s happening with pointer = result. Can anyone explain, or link to a good explanation of the theory?

``````sorted_val = sorted(values)
'''
I know the next section is supposed to start creating
a linked list by iterating through the sorted values
but am unclear how.
'''
# I know this is initialisng the final linked list
# what is happening here? I think this is the key point I'm struggling with
# we're only updating pointer in the for loop, but that's changing result
# How?
pointer = result
for val in sorted_val:
print(f'result is {result}, pointer is {pointer}')
pointer = pointer.next
# I understand the .next removes the first "0" that we added when creating the linked list
return result.next
``````

I was going to ask this question on stackoverflow but there have been quite a few similar questions - unfortunately, none of them are very clear to me. Bartosz Zaczyński RP Team

@Elise Ratcliffe The solution presented in the video boils down to the following three high-level steps:

1. Go through each individual linked list and unpack the stored values onto a flat list
2. Sort the list of unpacked values
3. Build a new linked list from the sorted values

It seems to me that you’re struggling to understand the last point, so I’ll try to break it down for you. Let’s use one of the examples from the video to try and visualize what’s going on:

• Linked lists (input):
• ① → ②
• ② → ④
• ③ → ③
• Unpacked values: 1, 2, 2, 4, 3, 3
• Sorted values: 1, 2, 2, 3, 3, 4
• Merged linked list (the expected output): ① → ② → ② → ③ → ③ → ④

So, now the question is, how do you wrap the sorted list of numbers into a corresponding linked list? Both are sequences, but every element of the linked list (called a node) must also point to the next element until there are no more elements. You can start by creating the first node (head) of your list:

``````head = Node(0)
``````

(I’m using slightly different variable and class names here to make my point across easier. Also, note that using `.next` as an attribute name shadows the built-in `next()` function. In cases like this, it’s customary to append a single underscore character to the variable name to avoid name conflicts, for example, `.next_`.)

`head` is going to be the first element of your resulting linked list. It can have any value at all, such as zero, because you’re going to discard that element later anyway. Your linked list looks like this at the moment: ⓪

Next, you go through the sorted values, then create the associated node element for each of the values, and hook the current node up to the previous node. To keep track of the previous node, you’ll need another helper variable. Let’s call it `previous` because we’ll use that variable to refer to the last node:

``````head = Node(0)

for value in sorted(values):
current = Node(value)
previous.next_ = current
``````

Initially, the previous node is set to the head of your resulting linked list. This will ensure that the head will now point to the current node with the desired value, for example: ⓪ → ①.

You must also remember to update the current value of the `previous` node so that the subsequent loop runs will move to the next node in your linked list:

``````head = Node(0)

for value in sorted(values):
current = Node(value)
previous.next_ = current
previous = current
``````

Otherwise, you’d always keep overwriting the `.next_` attribute of the head, ending up with something like ⓪ → ④ as a result. You can rewrite the code snippet above without using the `current` helper variable, which is similar to the solution in the video:

``````head = Node(0)

for value in sorted(values):
previous.next_ = Node(value)
previous = previous.next_
``````

When the loop finishes, you’ll have created the following linked list: ⓪ → ① → ② → ② → ③ → ③ → ④. Finally, you can use `head.next_` to discard the extra node that you created in the beginning:

``````head = Node(0)

for value in sorted(values):
previous.next_ = Node(value)
previous = previous.next_

``````

So, your linked list will not contain the initial head but only the nodes with the desired values: ① → ② → ② → ③ → ③ → ④.

Here’s the complete solution with an example:

``````from dataclasses import dataclass

@dataclass
class Node:
value: int
next_: "Node" = None

for value in sorted(unpack_values(linked_lists)):
previous.next_ = Node(value)
previous = previous.next_

if __name__ == '__main__':
print(merge([
Node(1, Node(2)),
Node(2, Node(4)),
Node(3, Node(3)),
]))
`````` James Carr

My solution before watching video 😬 ..

``````def merge_k_linked_lists(linked_lists):
nodes = []