You are given k sorted linked lists. Merge them all into one sorted list.
DSA Animator › DSA Revision › Linked List › Merge K Sorted Lists
Remember: a heap of size k holds one candidate from each list. Each pop gives the next smallest node. The video solves Merge K Sorted Lists (LeetCode 23, Hard) with the Heap Merge pattern from the Linked List topic, and you can replay every step in the interactive Merge K Sorted Lists animation.
You are given k sorted linked lists. Merge them all into one sorted list.
For 1, 4, 5 and 1, 3, 4 and 2, 6, the result is 1, 1, 2, 3, 4, 4, 5, 6.
Merging the lists one by one into the result costs O of k times n in total. A min heap always knows the smallest head.
Put the head of each list into a min heap. Pop the smallest node, attach it to the result, and push its next node if it exists. Repeat until the heap is empty.
The heap starts with 1, 1 and 2. Pop 1 from the first list and push 4, then pop 1 from the second list and push 3. Pop 2 and push 6, then pop 3 and push 4. Pop 4, 4, 5 and 6. The result is 1, 1, 2, 3, 4, 4, 5, 6.
In code, a priority queue orders nodes by value. Add every non-null head. While it is not empty, poll a node, link it to the tail, and offer its next. It's O of n log k time and O of k space.
Remember: a heap of size k holds one candidate from each list. Each pop gives the next smallest node.