 # 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. 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 Ö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):

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