Merge k sorted linked lists and return it as one sorted list.

Function Signature:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

from typing import List

def merge_k_sorted_lists(lists: List[ListNode]) -> ListNode:
    """
    Merge k sorted linked lists into one sorted list.

    Parameters:
    - lists: List of ListNode objects representing sorted linked lists.

    Returns:
    - ListNode: The head of the merged sorted list.
    """
    # Your code here

Example:

# Input: lists = [
#   1 -> 4 -> 5,
#   1 -> 3 -> 4,
#   2 -> 6
# ]
# Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
# Explanation: Merging the given sorted linked lists results in one sorted list.

# Input: lists = []
# Output: None
# Explanation: Merging an empty list of sorted linked lists results in None.

Note:

  • The linked lists are in sorted order.

Instructions:

  • Write the merge_k_sorted_lists function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊