Technical Interview Question:

You are given k sorted linked lists. Merge the k sorted linked lists into one sorted linked list and return it.

Example:

Input: lists = [[1->4->5], [1->3->4], [2->6]]

Output: [1->1->2->3->4->4->5->6]

Answer:

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeKLists(lists):
    # Create a dummy node to start the merged list
    dummy = ListNode(0)
    curr = dummy
    heap = []
    
    # Add the head of each list to a min heap
    for node in lists:
        if node:
            heap.append((node.val, node))
    heapq.heapify(heap)
    
    # Process the lists until the heap is empty
    while heap:
        # Pop minimum node from the heap and add it to the merged list
        val, node = heapq.heappop(heap)
        curr.next = ListNode(val)
        curr = curr.next
        # If the popped node has a next, push the next node to the heap
        if node.next:
            heapq.heappush(heap, (node.next.val, node.next))
    
    return dummy.next

Explanation:

1. We define a mergeKLists function that takes a list of linked lists as input.

2. We start by creating a dummy node to be the head of our merged list. We also initialize a curr node to keep track of the current node in the merged list.

3. Additionally, we create a heap array to store the head of each list, while also maintaining the ascending order.

4. We then iterate through the input lists and add their heads to the heap.

5. We use heapq.heapify() to maintain the heap property. This will ensure that the minimum element is always at the top of the heap.

6. We then start the merging process by popping the minimum node from the heap. We add this node to the merged list and move the curr pointer forward.

7. If the popped node has a next node, we add this next node to the heap.

8. We continue this process until the heap is empty and return the merged list starting from dummy.next.

This algorithm has a time complexity of O(N log(k)) where N is the total number of elements in all lists, and k is the number of lists. This is due to the heap operations for k lists.