Программа Javascript для выравнивания связанного списка

Дан связанный список, в котором каждый узел представляет собой связанный список и содержит два указателя своего типа:

1. Указатель на следующий узел в основном списке (в приведенном ниже коде мы называем его «правильным» указателем).
2. Указатель на связанный список, к которому относится этот узел (мы называем его указателем «вниз» в приведенном ниже коде).

Все связанные списки отсортированы. См. следующий пример

       5 -> 10 -> 19 -> 28
       |    |     |     |
       V    V     V     V
       7    20    22    35
       |          |     |
       V          V     V
       8          50    40
       |                |
       V                V
       30               45

Напишите функцию flatten(), чтобы объединить списки в один связанный список. Плоский связанный список также должен быть отсортирован. Например, для вышеуказанного входного списка выходной список должен быть 5->7->8->10->19->20->22->28->30->35->40->45->50. .

Идея состоит в том, чтобы использовать процесс Merge() сортировки слиянием для связанных списков. Мы используем merge() для объединения списков один за другим. Мы рекурсивно объединяем (merge()) текущий список с уже сглаженным списком.
Указатель вниз используется для связывания узлов сглаженного списка.

Ниже приведена реализация вышеуказанного подхода:

Выход:

5 7 8 10 19 20 20 22 30 35 40 45 50

Временная сложность: O(N*N*M) — где N — количество узлов в основном связанном списке (достижимых с помощью правого указателя), а M — количество узлов в отдельном подчиненном списке (доступном с помощью указателя вниз).
Сложность пространства: O(N*M), так как рекурсивные функции будут использовать рекурсивный стек размером, эквивалентным общему количеству элементов в списках.

Пожалуйста, обратитесь к полной статье о выравнивании связанного списка для получения более подробной информации!