如何在恒定空间中对单链表进行排序? [英] 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.next = 下一项.

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

我该怎么做?

推荐答案

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

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屋！