Merge K Sorted Lists

Problem Statement

Given an array of

linked lists, merge them into a single sorted linked list. The linked lists are all sorted in non-decreasing order.

Rules and Constraints

• You can assume that the input linked lists are not empty.
• The linked lists are sorted in non-decreasing order.
• Your solution should merge the linked lists into a single sorted linked list.
• You can modify the given linked lists while merging them.
• You cannot create a new linked list for the result.
• The length of the merged linked list is equal to the sum of the lengths of the individual input linked lists.
• You can only use a single data structure (or data type) to store the merged linked list.

Time Complexity: The time complexity of your solution should be O(N log k), where N is the total number of nodes across all input linked lists and k is the number of input linked lists. This is because each node is visited at most once for sorting, and the merge operation takes O(k) time for each node.

Space Complexity: The space complexity of your solution should be O(N), where N is the total number of nodes across all input linked lists. This is because all nodes from the input linked lists need to be stored in the merged linked list.

Note: This problem requires you to develop an efficient algorithm to merge the input linked lists while maintaining their sorted order. The algorithm should be able to handle a large number of input linked lists and nodes efficiently.

Example

Input: {"lists":[[1,4,5],[1,3,4],[2,6]]} Output: [1,1,2,3,4,4,5,6]