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:
return f"Link({self.val})"
return f"Link({self.val}, {self.next})"
def merge_k_linked_lists(linked_lists):
'''
Merge k sorted linked lists into one
sorted linked list.
>>> print(merge_k_linked_lists([
... Link(1, Link(2)),
... Link(3, Link(4))
... ]))
Link(1, Link(2, Link(3, Link(4))))
>>> print(merge_k_linked_lists([
... Link(1, Link(2)),
... Link(2, Link(4)),
... Link(3, Link(3)),
... ]))
Link(1, Link(2, Link(2, Link(3, Link(3, Link(4))))))
'''
```

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.

belushkinon April 27, 2020My solution before watching video:

I guess complexity would be: log(N) for priority queue and 2

N for for list traversal. So it would be Nlog(N)