LeetCode Meditations: Merge K Sorted Lists
Tags: computerscience, algorithms, typescript, javascript
Published: 2024-04-10 00:54:44

The description of [Merge K Sorted Lists](https://leetcode.com/problems/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](https://www.youtube.com/watch?v=q5a5OiGbT6Q) made a lot of sense. 

The way to go for a solution is the [Merge Sort algorithm](https://en.wikipedia.org/wiki/Merge_sort), 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:

```js
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:

```ts
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:

```ts
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:

```ts
/**
 * 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 {% katex inline %} O(n \ log \ k) {% endkatex %} — also see [NeetCode's explanation](https://youtu.be/q5a5OiGbT6Q?si=NlxKdlyZ5P2bsQUX&t=195) —, if you remember that the time complexity of the Merge Sort function is {% katex inline %} O(n \ log \ n) {% endkatex %}: We go through each item in the merging operation, but since the input is halved each time, we do it {% katex inline %} log \ n {% endkatex %} times. It is similar here, where {% katex inline %} n {% endkatex %} refers to the number of nodes, and {% katex inline %} k {% endkatex %} is the number of lists.
The space complexity is {% katex inline %} O(k) {% endkatex %} where {% katex inline %} k {% endkatex %} 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](https://en.wikipedia.org/wiki/Tree_(data_structure)). Until then, happy coding.