如何在恒定空间中对单链表进行排序?
我有一个单向链表，由于内存限制，我需要在恒定空间中对其进行排序(换句话说，不应使用与列表中项目数成正比的额外空间).
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; andhead.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
相关文章