Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Merge Multiple Sorted Lists (Main Thread)

Here is the interview question prompt, presented for reference.

You're given an array of multiple sorted linked lists. Can you write a method that returns it transformed into a single sorted linked list?

Each linked list can be represented as a series of nodes with the following definition:

function Node(val) {
  this.value = val;
  this.next = null;
}

Here's how it would be invoked:

// Input
const arr = [
  2 -> 6 -> 9,
  1 -> 2 -> 7,
  2 -> 6 -> 10
]

mergeLists(arr);

// Output
1 -> 2 -> 2 -> 2 -> 6 -> 6 -> 7 -> 9 -> 10

Constraints

  • Each list can have up to 100000 nodes
  • The cumulative sum of all the nodes in the linked lists will be <= 100000
  • The values in the nodes will be in the range -1000000000 and 1000000000
  • Let n and k be the length of a linked list and number of lists
  • Expected time complexity : O(n*k*log k)
  • Expected space complexity : O(k)

You can see the full challenge with visuals at this link.

Challenges • Asked over 6 years ago by Jake from AlgoDaily

Jake from AlgoDaily Commented on Nov 30, 2017:

This is the main discussion thread generated for Merge Multiple Sorted Lists.