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

Быстрая сортировка в двусвязном списке обсуждается здесь. Быстрая сортировка по односвязному списку дана в качестве упражнения. Важными вещами в реализации являются то, что она изменяет указатели, а не обменивает данные, а временная сложность такая же, как и реализация для двусвязного списка.

В partition() мы рассматриваем последний элемент как точку опоры. Мы проходим по текущему списку, и если узел имеет значение больше, чем точка поворота, мы перемещаем его после хвоста. Если узел имеет меньшее значение, мы сохраняем его в текущей позиции.

В QuickSortRecur() мы сначала вызываем partition(), который помещает точку поворота в правильную позицию и возвращает точку поворота. После того, как точка поворота помещена в правильное положение, мы находим хвостовой узел левой стороны (список перед точкой поворота) и повторяемся для левого списка. Наконец, мы повторяемся для правильного списка.

Выход:

Linked List before sorting 
30 3 4 20 5 
Linked List after sorting 
3 4 5 20 30 

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