Solution: Merge K Sorted Lists

Statement

Given an array of $k$ sorted linked lists, your task is to merge them into a single sorted linked list and return the head of this linked list.

Constraints:

• $k =$ lists.length
• $0 \leq k \leq 10^3$
• $0 \leq$ lists[i].length $\leq 500$
• $-10^3 \leq$ lists[i][j] $\leq 10^3$
• Each lists[i] is sorted in ascending order.
• The sum of all lists[i].length will not exceed $10^3$.

Solution

Since our task involves multiple lists, we can use the divide and conquer technique, starting with pairing the lists and then merging each pair. We repeat this until all the given lists are merged. This way, after the first pairing, we’re left with $\frac{k}{2}$ lists, then $\frac{k}{4}$, $\frac{k}{8}$ and so on.