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

Сортировка слиянием часто предпочтительнее для сортировки связанного списка. Низкая производительность произвольного доступа к связному списку делает некоторые другие алгоритмы (такие как быстрая сортировка) плохо работающими, а другие (такие как пирамидальная сортировка) полностью невозможными.

Пусть head будет первым сортируемым узлом связанного списка, а headRef будет указателем на head. Обратите внимание, что нам нужна ссылка на заголовок в MergeSort(), поскольку приведенная ниже реализация изменяет следующие ссылки для сортировки связанных списков (а не данных в узлах), поэтому необходимо изменить заголовок узла, если данные в исходном заголовке не являются наименьшее значение в связанном списке.

MergeSort(headRef)
1) If the head is NULL or there is only one element in the Linked List 
    then return.
2) Else divide the linked list into two halves.  
      FrontBackSplit(head, &a, &b); /* a and b are two halves */
3) Sort the two halves a and b.
      MergeSort(a);
      MergeSort(b);
4) Merge the sorted a and b (using SortedMerge() discussed here) 
   and update the head pointer using headRef.
     *headRef = SortedMerge(a, b);

Временная сложность: O(n*log n)

Космическая сложность: O(n*log n)

Подход 2: этот подход проще и использует пространство log n.

Сортировка слиянием():

1. Если размер связанного списка равен 1, верните голову
2. Найдите мид, используя подход Черепахи и Зайца.
3. Сохраните следующий из середины в head2, т. е. в правильном связанном списке.
4. Теперь сделайте следующую среднюю точку нулевой.
5. Рекурсивно вызовите mergeSort() как для левого, так и для правого подчиненного списка и сохраните новый заголовок левого и правого связанного списка.
6. Вызовите функцию merge() с учетом новых заголовков левого и правого связанных списков и сохраните последний заголовок, возвращенный после слияния.
7. Вернуть последний заголовок объединенного связанного списка.

слияние (голова1, голова2):

1. Возьмите указатель, скажем, слитый, чтобы сохранить в нем объединенный список и сохранить в нем фиктивный узел.
2. Возьмите временный указатель и назначьте ему слияние.
3. Если данные head1 меньше, чем данные head2, то сохраните head1 в следующем из temp и переместите head1 в следующий из head1.
4. В противном случае сохраните head2 в следующем из temp и переместите head2 в следующий из head2.
5. Переместить temp к следующему из temp.
6. Повторяйте шаги 3, 4 и 5, пока head1 не будет равен нулю, а head2 не равен нулю.
7. Теперь добавьте все оставшиеся узлы первого или второго связанного списка в объединенный связанный список.
8. Вернуть следующий из объединенных (который будет игнорировать манекен и вернуть заголовок окончательного объединенного связанного списка)

Выход:

Sorted Linked List is: 
2 3 5 7 10 20 

Временная сложность : O (n * log n)

Космическая сложность: O(log n)

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