Merge k sorted linked lists
DSA, Hard
Which structure or algorithm, and what does it cost.
A node has val and next. You get a list lists of k heads. Each list is already sorted in ascending order, and some may be null. Merge them into one sorted linked list and return its head. Reuse the existing nodes. Return null if there are no nodes at all.
Examples
Input [1->4->5, 1->3->4, 2->6]
Output 1->1->2->3->4->4->5->6
Why all the values from the three lists, in ascending order.
Input []
Output null
Why because there are no lists.
Input [null, 5->6]
Output 5->6
Why empty lists are skipped.
Constraints
- 0 <= k <= 10,000.
- Total number of nodes N <= 500,000.
- Values are integers in [-10,000, 10,000]. Equal values across lists are common.
Your answer must contain
- A simple method and its cost in k and N; a faster method and why it is faster; code for the faster one; time and memory; a hand trace of example 1 for the first three outputs.