如何在恒定空间中对单个链表进行排序？

I have a singly linked list and I need to sort it in constant space due to memory limitations (in other words, no extra space should be used that is proportional to the number of items in the list).

我有一个单链表,由于内存限制,我需要在常量空间中对其进行排序(换句话说,不应使用与列表中项目数成比例的额外空间)。

The structure of the linked list is:

链表的结构是:

head.item = the payload you want to sort on; and

head.item =您要排序的有效负载;和

head.next = the next item.

head.next =下一个项目。

The requirement for constant space discounts solutions where I build another list, I need to do it in-place.

对于我建立另一个列表的恒定空间折扣解决方案的要求,我需要就地进行。

How can I do that?

我怎样才能做到这一点?

4 个解决方案

#1

Sorting a linked list in constant space is easy, you just have to adjust the pointers. The easiest way to do this is to use a sort algorithm that only swaps adjacent elements. I'm going to provide a bubble-sort, just because you've made no requirement for efficiency:

在常量空间中对链表进行排序很容易,您只需调整指针即可。最简单的方法是使用仅交换相邻元素的排序算法。我将提供一个冒泡排序,只是因为你没有要求效率:

# 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

#2

A few methods:

几种方法:

use bubble sort on the list in place, this should be fast enough if the list is small

在列表中使用冒泡排序,如果列表很小,这应该足够快

copy the list to an array and use heapsort or quicksort then copy it back

将列表复制到数组并使用heapsort或quicksort然后将其复制回来

use bogosort on the list in place. The best case complexity is O(n) so it should be really fast*

在名单上使用bogosort。最好的案例复杂性是O(n)所以它应该非常快*

*note that the expected runtime complexity is O(n*n!)

*请注意,预期的运行时复杂度为O(n * n!)

#3

As this is obviously homework I would recommend:
You should know how to swap two elements of you list. Then pick a Sorting Algorithm and implement it.

因为这显然是家庭作业,我建议:你应该知道如何交换你列表中的两个元素。然后选择一个排序算法并实现它。

#4

For in-place sorting of a linked list, I would suggest merge sort. It's stable, and runs in NlgN time.

对于链接列表的就地排序,我建议合并排序。它很稳定,并且在NlgN时间内运行。

#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

#2