Practice/Amazon/Leetcode 23. Merge k Sorted Lists

Leetcode 23. Merge k Sorted Lists

CodingMust

Problem

You are given an array containing the head nodes of multiple sorted linked lists. Each linked list is sorted in ascending order. Your task is to merge all of these linked lists into a single sorted linked list and return the head of the merged list.

The merged list should be constructed by connecting the nodes from the input lists together, maintaining ascending order throughout.

Requirements

1. Merge all k linked lists into one sorted linked list
2. The final list must maintain ascending order
3. Return the head node of the merged linked list
4. Handle edge cases including empty input arrays and empty linked lists

Constraints

• The number of linked lists k is in the range [0, 10^4]
• The number of nodes in each list is in the range [0, 500]
• Node values are in the range [-10^4, 10^4]
• Each linked list is sorted in non-decreasing order
• The total number of nodes will not exceed 10^4

Examples

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked lists are: 1->4->5 1->3->4 2->6 Merging them into one sorted list gives: 1->1->2->3->4->4->5->6

Example 2:

Input: lists = [] Output: [] Explanation: No lists to merge results in an empty list.

Example 3:

Input: lists = [[]] Output: [] Explanation: The input contains one empty list, so the output is also empty.

Example 4:

Input: lists = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,3,4,5,6,7,8,9] Explanation: All lists have non-overlapping ranges, so they concatenate in order.