Merge k Sorted Lists
hardBlind 75NeetCode 150linked-listheapdivide-and-conquer
Problem
Given an array of k singly linked lists, each sorted ascending, merge them all into one sorted linked list and return its head.
Examples
Input: [1->4->5, 1->3->4, 2->6]
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
All nodes merged in sorted order.
Constraints
- • 0 <= k <= 10^4
- • Total nodes up to 10^4
- • Each input list is sorted ascending
Hints(tap to reveal)
- 1. A min-heap of list heads always yields the next node.
- 2. Alternatively merge lists pairwise like merge sort.
Optimal approach(spoiler)
- Push the head of each list into a min-heap keyed by value.
- Repeatedly pop the smallest node and append it to the output.
- Push that node's successor if one exists.
- Continue until the heap empties.
- O(N log k) time where N is total nodes, O(k) heap space.
Ready to solve it?
Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.
Practice in the editor