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 constraints (in other words, the extra space should not be used, which is proportional to the number of items in the list).
Linked list structure:
-
head.item
= the payload you want to sort; and -
head.next
= next item.
The requirement for permanent space discount decisions where I am building another list, I need to do it locally.
How can i do this?
a source to share
Sorting the linked list in constant space is easy, you just need to set up the pointers. The easiest way to do this is to use a sorting algorithm that only replaces adjacent elements. I'm going to provide a bubble view just because you didn't demand 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
a source to share
Several methods:
- use bubble sort in the list in place, this should be fast enough if the list is small
- copy the list to an array and use heapsort or quicksort then copy it.
- use bogosort in the list in place. The hardest task is
O(n)
, so it should be very fast *
* note that the expected complexity of execution O(n*n!)
a source to share
Since this is obviously homework, I would recommend:
You should know how to swap two list items. Then select a Sorting Algorithm and implement it.
a source to share