DEV Community

Cover image for LeetCode Meditations: Merge K Sorted Lists
Eda
Eda

Posted on • Originally published at rivea0.github.io

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
Enter fullscreen mode Exit fullscreen mode

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();
  }
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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];
};
Enter fullscreen mode Exit fullscreen mode
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;
}
Enter fullscreen mode Exit fullscreen mode

Time and space complexity

The time complexity is O(n log k)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)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 nlog \ n times. It is similar here, where nn refers to the number of nodes, and kk is the number of lists.
The space complexity is O(k)O(k) where kk 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.

Reinvent your career. Join DEV.

It takes one minute and is worth it for your career.

Get started

Top comments (0)

This post blew up on DEV in 2020:

js visualized

🚀⚙️ JavaScript Visualized: the JavaScript Engine

As JavaScript devs, we usually don't have to deal with compilers ourselves. However, it's definitely good to know the basics of the JavaScript engine and see how it handles our human-friendly JS code, and turns it into something machines understand! 🥳

Happy coding!

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay