Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!philabs!cmcl2!harvard!seismo!topaz!bentley!mdr
From: mdr@bentley.UUCP (M. Rossner)
Newsgroups: net.lang.c
Subject: Sorting linked list
Message-ID: <669@bentley.UUCP>
Date: Thu, 27-Mar-86 14:55:45 EST
Article-I.D.: bentley.669
Posted: Thu Mar 27 14:55:45 1986
Date-Received: Sun, 20-Apr-86 11:28:47 EST
Organization: AT&T Bell Laboratories, Liberty Corner
Lines: 47

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! --