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.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

function mergeLists(arrOfLists) {

  if (!arrOfLists || arrOfLists.length === 0) {

    return [];

  }

​

  let pq = new PriorityQueue();

  for (let list of arrOfLists) {

    if (list) {

      let currentNode = list;

      pq.insert(currentNode.val);

​

      while (currentNode.next) {

        pq.insert(currentNode.next.val);

        currentNode = currentNode.next;

      }

    }

  }

  return pq.first || [];

}

​

// Supporting data structures

​

class PriorityQueue {

  constructor() {

    this.first = null;

    this.size = 0;

  }

​

  insert(val) {

    const newNode = new Node(val);

Got more time? Let's keep going.

If you had any problems with this tutorial, check out the main forum thread here.