https://www.geeksforgeeks.org/flattening-a-linked-list/

flattening-a-linked-list.js

// https://www.geeksforgeeks.org/flattening-a-linked-list/
// https://www.youtube.com/watch?v=PSKZJDtitZw
function printList(root) {
  let tmp = root;
  let arr = [];
  while (tmp) {
    arr.push(tmp.val);
    tmp = tmp.down;
  }
  return arr;
}

class Node {
  constructor(val, right, down) {
    this.val = val;
    this.right = right;
    this.down = down;
  }
}

function merge(a, b) {
  if (!a) return b;
  if (!b) return a;
  let result;
  if (a.val < b.val) {
    result = a;
    result.down = merge(a.down, b);
  } else {
    result = b;
    result.down = merge(a, b.down);
  }
  return result;
}

function flatten(node) {
  if (!node || !node.right) return node;
  return merge(node, flatten(node.right));
}

const vNode1 = new Node(7, null, new Node(8, null, new Node(30)));
const vNode2 = new Node(20);
const vNode3 = new Node(22, 50);
const vNode4 = new Node(35, null, new Node(40, null, new Node(45)));
const head = new Node(5,
  new Node(10,
    new Node(19,
      new Node(28, null, vNode4),
    vNode3),
  vNode2),
vNode1);
// console.log(head);
const res = flatten(head);
console.log(printList(res).join(',') === '5,7,8,10,19,20,22,28,30,35,40,45');