>However, I think I'm right in saying that I'd need a doubly-linked list to do this?
Insertion sort doesn't require a doubly linked list, but you will find that building a new list as you break down the old one is the easiest solution:
Code:
struct node *sort_list ( struct node *in )
{
struct node out = {0,0};
struct node *i, *step, *next;
for ( step = in; step != 0; step = next ) {
next = step->next;
for ( i = &out; i->next != 0; i = i->next ) {
if ( i->next->data > step->data )
break;
}
step->next = i->next;
i->next = step;
}
return out.next;
}
-Prelude