Merge three lists
Input
[[1,4,5],[1,3,4],[2,6]]
Output
[1, 1, 2, 3, 4, 4, 5, 6]
All lists are merged into one sorted list.
Full lesson preview
Merge k sorted lists
Merge k sorted linked lists into one sorted list. Input lists are provided as Python lists of values.
Python practice25 minLinked ListsAdvancedLast updated March 27, 2026
Problem statement
Given a list of k sorted singly linked lists (each represented as a Python list of values), merge them into one sorted linked list and return the values as a Python list.
You should handle empty lists, duplicate values, and varying lengths of lists. Aim for O(N log k) or O(N log k)-like behavior where N is total number of elements, or a clean divide-and-conquer merging strategy.
Task
Combine k sorted sequences into one sorted list efficiently.
Examples
Input format
A list of k Python lists, each already sorted in non-decreasing order.
Output format
A single Python list containing all elements in non-decreasing order.
Constraints
- Total number of elements across all lists is up to 10^4 (practical tests small)
- Values are integers and may include negatives and duplicates
Prefer an approach that scales well with k (e.g., divide-and-conquer or heap-based merging).
Samples
Sample 1
Input
[[], []]
Output
[]
Two empty lists merge to an empty list.