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:

xxxxxxxxxx

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;

    }

  }

}