LeetCode 23: Merge k Sorted Lists - Interview Prep Ep 26

preview_player
Показать описание

LeetCode 23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Solution explained:
1. We can use a min heap (PriorityQueue) to hold all of the k head nodes of all k sorted linked lists, so that each time, we could quickly get the node with the current minimum value that'd be added into the final result;
2. We first go through the given array of linked list heads, enqueue all of the k heads into the min heap, when we'll constantly check the min heap, each time, we poll one out of the min heap, we do two things:
a. we add this node (create a new list node with this value) into the final merged result;
b. check if this head still has any nodes after it, if so, move the pointer towards its next one and enqueue the next one into the min heap

⭐ Support my channel and connect with me:

// TOOLS THAT I USE:

// MY FAVORITE BOOKS:

My ENTIRE Programming Equipment and Computer Science Bookshelf:

And make sure you subscribe to my channel!

Your comments/thoughts/questions/advice will be greatly appreciated!

#softwareengineering #leetcode #algorithms #coding #interview #SDE #SWE #SiliconValley #programming #datastructures
Рекомендации по теме
Комментарии
Автор

great explanation of the complexity, many other videos didn't mention this!

luqio
Автор

Hey Fisher, I've been watching your videos and really have to say your detailed explanations are really good! I am trying to do better on the transition from explanation to code. Your explanations really help give a concrete understanding. I also really enjoy the process and high efficiently of your solutions. They are a bit more complex than other solutions in terms of coding concepts. However I think that a good thing! I hope by continuing the process and coding side by side with you I can improve in my development skills. Much love and appreciation :)

louismontes
Автор

Actually I think that the space is O(N+K) as in the line 22 you are aways creating a new ListNode. If you replace this line by "tmp.next = curr;" on that case you have O(K) as you are using the same ListNode reference of the input;

leonardoagarcia
Автор

(o1, o2)-> o1.val-o2.val, what does this do please explain. i am not able to get that clearly. Thanks!

akashbhadouria
Автор

Fisher, what's the difference between add and offer function, remove and poll function in priorityqueue, they look the same to me ?

yitingg
Автор

my code won't pass because certain test case is lists = [ ]
when I define node the val will be 0, so :

Input : [ ]
Output: [0]
Expected: [ ]

hmm what should I do ? the problem I need to return node fro mthe function..

enditend