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; andhead.next = the next item.The requirement for constant space discounts solutions where I build another list, I need to do it in-place.
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
For in-place sorting of a linked list, I would suggest merge sort. It's stable, and runs in NlgN time.
A few methods:
O(n) so it should be really fast**note that the expected runtime complexity is O(n*n!)
