如何在常量空间中排序单链表？ [英] How can I sort a singly linked list in constant space?

问题描述

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

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).

链接列表的结构是：

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

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

对于恒定空间折扣解决方案的需求，我建立另一个列表，我需要在原地。

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

我如何做？ / p>

How can I do that?

推荐答案

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

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

这篇关于如何在常量空间中排序单链表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！