Merge K (Multiple) Sorted Lists

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)

```js
function mergeLists(arrOfLists) {
  return arrOfLists;
}

const ll1 = new Node(2);
ll1.next = new Node(6);
ll1.next.next = new Node(9);
const ll2 = new Node(1);
ll2.next = new Node(2);
ll2.next.next = new Node(7);
const ll3 = new Node(2);
ll3.next = new Node(6);
ll3.next.next = new Node(10);
let final = mergeLists([ll1, ll2, ll3])
```

This is a more difficult problem than it may initially seem!

An obvious brute force solution is simply to:

1. Traverse through every list
2. Store all the node values in an array
3. Sort the array. Unfortunately here, the time complexity is O(n log n) since there are n total nodes and sorting takes O(n log n) time.

We can improve on the brute force approach by instead comparing node to node, and putting them in the right order as we're traversing. This becomes very similar to the Merged Sorted Linked Lists problem.

A better approach is to introduce a data structure. We need something that is built to process and order elements one by one in an efficient manner. What about a priority queue?

A priority queue is an abstract data type used to maintain a queue, with each element having a concept of a priority or order to be served.

Let's start by implementing one with a simple insert method:

```js
class PriorityQueue {
	constructor() {
		this.first = null;
		this.size = 0;
	}

	insert(val) {
		// decide where in the queue it falls
    const newNode = new Node(val);
    // if there's no first node or this new node is higher priority, move it to first
		if (!this.first || newNode.val < this.first.val) {
			newNode.next = this.first;
			this.first = newNode;
		} else {
			// if it's a lower priority on the queue by value
			let currNode = this.first;

			// keep iterating until we find a node whose value we are greater than
			while (currNode.next && newNode.val > currNode.next.val) {
				currNode = currNode.next;
			}
			newNode.next = currNode.next;
			currNode.next = newNode;
		}
	}
}
```

Then, using it is a matter of running the linked lists through it:

```js
let pq = new PriorityQueue();
for (let list of arrOfLists) {
  if (list) {
    let currentNode = list;
    pq.insert(currentNode.val);

    // process the rest of the list
    while (currentNode.next) {
      pq.insert(currentNode.next.val);
      currentNode = currentNode.next;
    }
  }
}

// returning this will return the head of the priority queue linked list result
return pq.first || [];
```

Don't forget to handle the case when the array is empty:

```js
if (!arrOfLists || arrOfLists.length === 0) {
  return [];
}
```

Let's put it all together now.

One Pager Cheat Sheet

• You can merge multiple sorted linked lists into a single sorted linked list, with time complexity of O(n*k*log k) and space complexity of O(k).
• We can improve the brute force solution to sorting a list of linked lists by introducing a Priority Queue data structure, which allows us to efficiently process and order elements one by one in O(n log n) time.
• The process involves running the linked lists through the designated software to achieve the desired result.
• Always check for an empty array before attempting any operations.
• Putting it all together is the key to achieving success.