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

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