#include <stdio.h>
#include <stdlib.h>

struct node {                    /* a node on a doubly linked list */
	int value;
	struct node *prev;
	struct node *next;
};

int main(int argc, char **argv)
{
	struct node *first = NULL;   /* List initially empty. */
	struct node *last = NULL;
	int i;
	struct node *p;

	printf("Type a series of integers, EOF (control-d) to quit.\n");

	while (scanf("%d", &i) == 1) {
		struct node *const n = malloc(sizeof (struct node));
		if (n == NULL) {
			fprintf(stderr, "%s: can't allocate %u bytes\n", /* not portable */
				argv[0], sizeof (struct node));
			return EXIT_FAILURE;
		}
		n->value = i;

		if (first == NULL) {
			/* Insert n into an empty list. */
			n->next = n->prev = NULL;
			first = last = n;
			continue;
		}

		if (i <= first->value) {
			/* Insert n before the first node on the list. */
			n->prev = NULL;
			n->next = first;
			first = first->prev = n;
			continue;
		}

		if (i > last->value) {
			/* Insert n after the last node on the list. */
			n->prev = last;
			n->next = NULL;
			last = last->next = n;
			continue;
		}

		for (p = first; i > p->value; p = p->next) {
		}

		/* Insert n between p->prev and p. */
		n->prev = p->prev;
		n->next = p;
		p->prev = p->prev->next = n;
	}

	printf("\nHere are the integers in increasing order:\n");

	for (p = first; p;) {
		struct node *const doomed = p;
		printf("%d\n", p->value);

		p = p->next;
		free(doomed);
	}

	return feof(stdin) && !ferror(stdin) ? EXIT_SUCCESS : EXIT_FAILURE;
}