LeetCode Meditations: Merge K Sorted Lists

The description of Merge K Sorted Lists states:

You are 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.

For example:

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:
1->1->2->3->4->4->5->6

---

This problem was a bit confusing to me at first, but the explanation by NeetCode made a lot of sense.

The way to go for a solution is the Merge Sort algorithm, which is one of the most familiar algorithms you might remember from any introductory computer science course.

Now, in a usual Merge Sort when we're given an array as the input, we recursively split the array into left and right halves, and keep merging them until the whole array is sorted. Here's how our familiar friend might look like in JavaScript:

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  let left = arr.slice(0, Math.floor(arr.length / 2));
  let right = arr.slice(Math.floor(arr.length / 2), arr.length);

  mergeSort(left);
  mergeSort(right);

  merge(left, right, arr);

  return arr;
}


function merge(left, right, arr) {
  let index = 0;

  while (left.length && right.length) {
    if (left[0] < right[0]) {
      arr[index++] = left.shift();
    } else {
      arr[index++] = right.shift();
    }
  }

  while (left.length) {
    arr[index++] = left.shift();
  }

  while (right.length) {
    arr[index++] = right.shift();
  }
}

However, what we're going to make use of is the idea of the merge function.

Since we're also using linked lists, it will look a bit different. Using TypeScript, it will look like this:

function merge(list1: ListNode | null, list2: ListNode | null) {
  let result = new ListNode(0);
  let currentNode = result;

  while (list1 !== null && list2 !== null) {
    if (list1.val < list2.val) {
      currentNode.next = list1;
      list1 = list1.next;
    } else {
      currentNode.next = list2;
      list2 = list2.next;
    }

    currentNode = currentNode.next;
  }

  if (list1 !== null) {
    currentNode.next = list1;
  }

  if (list2 !== null) {
    currentNode.next = list2;
  }

  return result.next;
}

Since we're given k sorted lists, we'll merge pairs of lists, and keep merging while the length of lists is greater than 1:

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  if (lists === null || lists.length === 0) {
    return null;
  }

  while (lists.length > 1) {
    let mergedLists = [];
    for (let i = 0; i < lists.length; i += 2) {
      let list1 = lists[i];
      let list2 = i + 1 < lists.length ? lists[i + 1] : null;
      mergedLists.push(merge(list1, list2));
    }

    lists = mergedLists;
  } 

  return lists[0];
};

Note
If list2 is null (in the case where the length of lists is not even), the merging of list1 and list2 will be just list1.

Overall, the solution looks like this:

/**
 * Definition for singly-linked list.
 * 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)
 *   }
 * }
 */

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  if (lists === null || lists.length === 0) {
    return null;
  }

  while (lists.length > 1) {
    let mergedLists = [];
    for (let i = 0; i < lists.length; i += 2) {
      let list1 = lists[i];
      let list2 = i + 1 < lists.length ? lists[i + 1] : null;
      mergedLists.push(merge(list1, list2));
    }

    lists = mergedLists;
  } 

  return lists[0];
};

function merge(list1: ListNode | null, list2: ListNode | null) {
  let result = new ListNode(0);
  let currentNode = result;

  while (list1 !== null && list2 !== null) {
    if (list1.val < list2.val) {
      currentNode.next = list1;
      list1 = list1.next;
    } else {
      currentNode.next = list2;
      list2 = list2.next;
    }

    currentNode = currentNode.next;
  }

  if (list1 !== null) {
    currentNode.next = list1;
  }

  if (list2 !== null) {
    currentNode.next = list2;
  }

  return result.next;
}

Time and space complexity

The time complexity is $O(n \ log \ k)$ — also see NeetCode's explanation —, if you remember that the time complexity of the Merge Sort function is $O(n \ log \ n)$ : We go through each item in the merging operation, but since the input is halved each time, we do it $log \ n$ times. It is similar here, where $n$ refers to the number of nodes, and $k$ is the number of lists.
The space complexity is $O(k)$ where $k$ is the number of lists as we keep a temporary mergedLists variable.

---

And, this is the last problem of the Linked Lists chapter. Next up, we'll begin looking at some trees. Until then, happy coding.