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

Дан односвязный список, содержащий n узлов. Проблема состоит в том, чтобы отсортировать список, используя технику рекурсивной сортировки выбором. Подход должен быть таким, чтобы он включал обмен ссылками узла вместо обмена данными узла.

Примеры:

Input: 10 -> 12 -> 8 -> 4 -> 6
Output: 4 -> 6 -> 8 -> 10 -> 12 

В сортировке выбором мы сначала находим минимальный элемент, меняем его местами с начальным узлом и повторяем для оставшегося списка. Ниже представлена рекурсивная реализация этих шагов для связанного списка.

recurSelectionSort(head)
     if head->next == NULL
         return head
     Initialize min = head
     Initialize beforeMin = NULL
     Initialize ptr = head
    
     while ptr->next != NULL 
         if min->data > ptr->next->data
         min = ptr->next
         beforeMin = ptr
     ptr = ptr->next    
    
     if min != head
         swapNodes(&head, head, min, beforeMin)
    
     head->next = recurSelectionSort(head->next)
     return head

swapNodes(head_ref, currX, currY, prevY)
     head_ref = currY
     prevY->next = currX

     Initialize temp = currY->next
     currY->next = currX->next
     currX->next  = temp    

swapNodes(head_ref, currX, currY, prevY) основан на обсуждаемом здесь подходе, но он был соответствующим образом изменен для реализации этого поста.

Выход:

Linked list before sorting:
10 12 8 4 6
Linked list after sorting:
4 6 8 10 12

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

Вспомогательное пространство: O(n)

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