Merge K Sorted linked lists

Question

Given two sorted graphs, merge them into a single sorted result.

Codemia · Accepted Answer

To merge K sorted linked lists, we can identify a suitable pattern for this problem: the **Min-Heap** or **Priority Queue** approach. This is because we need to continuously extract the smallest element from the heads of all K lists and maintain their order. A Min-Heap allows efficient retrieval of the minimum element in logarithmic time, which is ideal for merging multiple sorted lists.

1. **Initialize a Min-Heap**: Start by creating a min-heap to hold the head nodes of all K linked lists. Each entry in the heap will contain a tuple of (node value, list index, node reference).

2. **Push Initial Nodes**: Iterate through each of the K linked lists and insert the head node into the heap.

3. **Merge Process**: 
   - While the heap is not empty, extract the minimum element (the smallest node).
   - Append this node to the result linked list.
   - If the extracted node has a next node, push that next node into the heap.

4. **Return Result**: After all nodes have been processed, return the merged linked list.

**Example**: Given lists:
- List 1: 1 -> 4 -> 5
- List 2: 1 -> 3 -> 4
- List 3: 2 -> 6

The min-heap will first contain (1, 0, List1_head), (1, 1, List2_head), (2, 2, List3_head). We will extract and build the merged list as: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6.

Here is the Python implementation of the above approach:

```python
import heapq

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

def mergeKLists(lists):
    min_heap = []
    # Initialize the heap with the head nodes of each linked list
    for i, l in enumerate(lists):
        if l:
            heapq.heappush(min_heap, (l.val, i, l))

# Create a dummy node to help build the merged list
    dummy = ListNode(0)
    current = dummy

while min_heap:
        # Get the smallest node
        val, idx, node = heapq.heappop(min_heap)
        current.next = node  # Append it to the merged list
        current = current.next  # Move to the next position
        # If there is a next node, push it into the heap
        if node.next:
            heapq.heappush(min_heap, (node.next.val, idx, node.next))

return dummy.next  # Return the merged list starting from the next node of dummy
```

The time complexity of this algorithm is **O(N log K)**, where N is the total number of nodes across all linked lists, and K is the number of linked lists. This is due to the fact that we perform a push and pop operation on the heap for each of the N nodes, and each operation takes O(log K) time.

The space complexity is **O(K)**, which is the space required to store the K head nodes in the heap.

1. **Empty Input**: If the input list `lists` is empty, we should return `None`. 
2. **Single List**: If there is only one linked list in the input, we simply return that linked list. 
3. **All Lists Empty**: If all linked lists are `None`, the result should also be `None`. 
4. **Single Node in Each List**: If each list contains only one node, the merging should still correctly output a merged linked list preserving the order.

Merge K Sorted linked lists

Mastercard

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Mastercard Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string