Merge k Sorted Lists - Video Solutions

Problem Overview: You receive k sorted linked lists and must merge them into one sorted linked list. The final list must preserve sorted order while efficiently handling all nodes across the input lists.

Approach 1: Sequential Merge (O(Nk) time, O(1) space)

The simplest idea merges lists one at a time. Start with the first list, merge it with the second, then merge the result with the third, and continue until all lists are processed. Each merge operation works like the classic merge step in merge sort, comparing node values and appending the smaller one to the result. The problem is repeated work: nodes from earlier lists get compared again every time a new list is merged. With N total nodes and k lists, the overall cost grows to O(Nk). This approach is easy to implement but inefficient when k is large.

Approach 2: Merge Using a Min-Heap (O(N log k) time, O(k) space)

A more scalable solution keeps track of the smallest current node across all lists using a min-heap. Push the head of every list into a heap keyed by node value. Repeatedly extract the smallest node, append it to the result list, and insert the next node from the same list into the heap. The heap size never exceeds k, so each push or pop costs O(log k). Since every one of the N nodes is inserted and removed exactly once, the total complexity becomes O(N log k) with O(k) extra space. This approach heavily relies on the heap (priority queue) data structure to efficiently track the smallest candidate node.

Approach 3: Divide and Conquer (O(N log k) time, O(log k) space)

This method applies the same strategy used by divide and conquer algorithms. Pair up lists and merge them in parallel: first merge list 1 with list 2, list 3 with list 4, and so on. After one pass, the number of lists halves. Repeat the process until only one list remains. Each level processes all N nodes, and there are log k levels of merging, leading to O(N log k) time complexity. Space usage is O(log k) if implemented recursively due to the call stack. The benefit is that each node participates in far fewer comparisons than in the sequential merge approach.

Recommended for interviews: The min-heap solution is the most commonly expected answer because it demonstrates knowledge of priority queues and efficient multi-way merging. The divide and conquer approach is equally optimal and often preferred when interviewers want to test algorithmic reasoning around recursive merging. Showing the sequential merge idea first demonstrates baseline understanding, while moving to the O(N log k) strategies shows strong optimization skills.