Программа 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 2 )
Вспомогательное пространство: O(n)
Пожалуйста, обратитесь к полной статье о рекурсивной сортировке для односвязного списка | Обмен ссылками узлов для более подробной информации!