Как я могу отсортировать односвязный список в постоянном пространстве?[закрыто]

Question

У меня есть односвязный список, и мне нужно отсортировать его в постоянном пространстве из-за ограничений памяти (другими словами, не следует использовать дополнительное пространство, пропорциональное количеству элементов в списке).

Структура связанного списка такова:

• head.item = полезная нагрузка, по которой вы хотите выполнить сортировку;и
• head.next = следующий элемент.

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

Как я могу это сделать?

Answer 1

Отсортировать связанный список в постоянном пространстве несложно, вам просто нужно настроить указатели.Самый простой способ сделать это - использовать алгоритм сортировки, который меняет местами только соседние элементы.Я собираюсь использовать пузырьковую сортировку только потому, что вы не предъявляли никаких требований к эффективности:

# Enter loop only if there are elements in list.

swapped = (head <> null)
while swapped:
    # Only continue loop if a swap is made.

    swapped = false

    # Maintain pointers.

    curr = head
    next = curr.next
    prev = null

    # Cannot swap last element with its next.

    while next <> null:
        # Swap if items in wrong order.

        if curr.item > next.item:
            # Notify loop to do one more pass.

            swapped = true

            # Swap elements (swapping head is special case).

            if curr == head:
                head = next
                temp = next.next
                next.next = curr
                curr.next = temp
                curr = head
            else:
                prev.next = curr.next
                curr.next = next.next
                next.next = curr
                curr = next
            endif
        endif

        # Move to next element.

        prev = curr
        curr = curr.next
        next = curr.next
    endwhile
endwhile

Answer 2

Несколько методов:

• используйте пузырьковую сортировку в списке на месте, это должно быть достаточно быстро, если список небольшой
• скопируйте список в массив и используйте heapsort или quicksort, затем скопируйте его обратно
• используйте bogosort в списке на месте.Сложность в лучшем случае такова O(n) так что это должно быть действительно быстро*

* обратите внимание, что ожидаемая сложность во время выполнения составляет O(n*n!)

Answer 3

Для сортировки связанного списка на месте я бы предложил сортировку слиянием.Он стабилен и работает в течение NlgN времени.