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

This approach uses a divide and conquer method to merge multiple sorted lists into a single sorted list. It initially pairs up the lists and merges each pair of lists. This merging of pairs produces $(\frac{k}{2})$ lists which, if merged produce $(\frac{k}{4})$ lists, and so on. This is repeated until we’re left with only one fully merged list. Merging a pair of lists uses two pointers, each pointing to a node in each list. If the node pointed by the first pointer has a value less than or equal to that pointed by the second one, it is added to the merged list. Otherwise, the value pointed by the second pointer is added. This is repeated until we have merged both lists into one. By merging each pair of lists, we end up with a single fully merged list at the end.