Sort a singly Linked list

Question

The structure of the linked list is

head.item = the number you want to sort
head.next = the next item

The only catch is that I need the singly linked list to sorted in constant space.

Answer 1

A few methods:

• use bubble sort on 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 back
• use bogosort on the list in place. The best case complexity is O(n) so it should be really fast*

*note that the expected runtime complexity is O(n*n!)

Answer 2

As this is obviously homework I would recommend:
You should know how to swap two elements of you list. Then pick a Sorting Algorithm and implement it.

Answer 3

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

Answer 4

What about std::slist
http://www.sgi.com/tech/stl/Slist.html