Sorting linked list

[M. Rossner]

It seems that there is an obvious recursive solution to this
problem that has not yet been mentioned.  To sort a linked list
(in place, without allocating ANY more memory), I just need to sort
everything except the first node and then insert the first node into
this list.

Note that this assumes a dummy header with a null key so that the
head of the list is constant.

sort (list)
struct foo *list;
{
	struct foo *current;

	if (list->next->next == NULL)       /* down to last node */
		return (list);
	else {
		current = list->next;
		list->next = current->next;
		sort (list);
		insert (list, current);
		return (list);
	}
}


insert (list, node)
struct foo *list, *node;
{
	struct foo *last, *current;

	last = list;
	current = list->next;
	while (node->key > current->key) {
		last = current;
		current = current->next;
	}
	last->next = node;
	node->next = current;
}

Voila! Less than tweny lines of code in its entirety.  Think recursive, man!

             Marc D. Rossner
		-- Hoping never to see you on this newsgroup again --
		-- In Cinema, televisia, et libra speramus       --
		-- To the Walking Lint, have a nice weekend! --