Solving Merge k Sorted Lists: Combining Multiple Sorted Lists

The "Merge k Sorted Lists" problem is about combining multiple sorted linked lists into one single sorted list.

Problem Statement

Given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked list and return it.

Example

Consider k sorted linked lists:

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 results in 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6.

Example 2

• Input: lists = []
• Output: []
• Explanation: No lists to merge, so the output is an empty list.

Example 3

• Input: lists = [[]]
• Output: []
• Explanation: A single empty list results in an empty merged list.

Solution Approach

A popular approach to solving this problem is using a Min Heap or a Priority Queue to efficiently find and merge the smallest elements of the lists.

Solution Approach - Min Heap

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

class MinHeap {
  private heap: Array<ListNode | null>;

  constructor() {
    this.heap = [];
  }

  private getLeftChildIndex(parentIndex: number): number {
    return 2 * parentIndex + 1;
  }

  private getRightChildIndex(parentIndex: number): number {
    return 2 * parentIndex + 2;
  }

  private getParentIndex(childIndex: number): number {
    return Math.floor((childIndex - 1) / 2);
  }

  private hasLeftChild(index: number): boolean {
    return this.getLeftChildIndex(index) < this.heap.length;
  }

  private hasRightChild(index: number): boolean {
    return this.getRightChildIndex(index) < this.heap.length;
  }

  private hasParent(index: number): boolean {
    return this.getParentIndex(index) >= 0;
  }

  private leftChild(index: number): ListNode | null {
    return this.heap[this.getLeftChildIndex(index)];
  }

  private rightChild(index: number): ListNode | null {
    return this.heap[this.getRightChildIndex(index)];
  }

  private parent(index: number): ListNode | null {
    return this.heap[this.getParentIndex(index)];
  }

  private swap(indexOne: number, indexTwo: number): void {
    const temp = this.heap[indexOne];
    this.heap[indexOne] = this.heap[indexTwo];
    this.heap[indexTwo] = temp;
  }

  public isEmpty(): boolean {
    return this.heap.length === 0;
  }

  public insert(node: ListNode | null): void {
    this.heap.push(node);
    this.heapifyUp();
  }

  public extract(): ListNode | null {
    if (this.isEmpty()) {
      return null;
    }
    const node = this.heap[0];
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop();
    this.heapifyDown();
    return node;
  }

  private heapifyUp(): void {
    let index = this.heap.length - 1;
    while (this.hasParent(index) && this.parent(index)!.val > this.heap[index]!.val) {
      this.swap(this.getParentIndex(index), index);
      index = this.getParentIndex(index);
    }
  }

  private heapifyDown(): void {
    let index = 0;
    while (this.hasLeftChild(index)) {
      let smallerChildIndex = this.getLeftChildIndex(index);
      if (this.hasRightChild(index) && this.rightChild(index)!.val < this.leftChild(index)!.val) {
        smallerChildIndex = this.getRightChildIndex(index);
      }

      if (this.heap[index]!.val < this.heap[smallerChildIndex]!.val) {
        break;
      } else {
        this.swap(index, smallerChildIndex);
      }
      index = smallerChildIndex;
    }
  }
}

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  const minHeap = new MinHeap();
  lists.forEach((list) => {
    if (list) minHeap.insert(list);
  });

  const dummy = new ListNode(0);
  let current = dummy;

  while (!minHeap.isEmpty()) {
    let node = minHeap.extract();
    current.next = node;
    if (current.next) {
      current = current.next;
    }
    if (node && node.next) {
      minHeap.insert(node.next);
    }
  }

  return dummy.next;
}

Breaking Down the Solution

The provided TypeScript solution for merging k sorted linked lists implements a custom Min Heap class and uses it to efficiently merge the lists. Here's a breakdown of how the solution works:

ListNode Class

• Represents a node in a linked list.
• Contains a value (val) and a reference to the next node (next).

MinHeap Class

• A min heap is a binary tree where the parent node is always less than or equal to its children.
• The class maintains a heap in an array (heap), where each element is a ListNode or null.

Key Methods and Properties:

• getLeftChildIndex, getRightChildIndex, getParentIndex: Calculate the indices of a node's left child, right child, and parent.
• hasLeftChild, hasRightChild, hasParent: Check if the node at the given index has a left child, right child, or parent.
• leftChild, rightChild, parent: Get the left child, right child, or parent of the node at the given index.
• swap: Swap two nodes in the heap.
• isEmpty: Check if the heap is empty.
• insert: Add a new node to the heap and reorganize the heap to maintain the min heap property (heapify up).
• extract: Remove and return the smallest node from the heap and reorganize the heap (heapify down).

mergeKLists Function

• Merges k sorted linked lists into one sorted linked list.
• Uses the Min Heap to efficiently find the smallest current node among all the lists.
• Iteratively extracts the smallest node from the heap and adds it to the merged list.
• If the extracted node has a next node, inserts the next node into the heap.

Process:

1. Initialize Min Heap: All head nodes of the k lists are inserted into the min heap.
2. Merging: Continuously extract the smallest node from the heap and attach it to the merged list.
3. Insert Next Nodes: If the extracted node has a next node, insert that next node into the heap to be considered in subsequent extractions.
4. Completion: The process continues until the heap is empty, meaning all nodes have been merged into the new list.

The result is a new linked list, pointed to by dummy.next, which is a sorted merge of all the input linked lists. This approach efficiently handles the merging process, making it suitable for a large number of lists or lists with a large number of nodes.

Conclusion

Merging k sorted lists is a classic problem that demonstrates the practical application of heap data structures in sorting and merging operations.