Merge K Sorted Lists

Hard · Linked List

You are given a list containing several linked lists, each of which is already sorted in ascending order. Merge all of them into a single linked list that remains sorted in ascending order and return its head. If there are no lists, or all of them are empty, return an empty result.

Examples

Input:  lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Why:    All the numbers from the three sorted lists are combined and arranged in increasing order.

Input:  lists = []
Output: []
Why:    There are no lists to merge, so the result is an empty list.

Input:  lists = [[]]
Output: []
Why:    The only list provided is empty, so nothing to merge.

Constraints

0 <= number of lists <= 10^4, 0 <= length of each list <= 500, -10^4 <= node value <= 10^4, total number of nodes across all lists <= 10^4

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Merge K Sorted Lists

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Merge K Sorted Lists. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.