quicksort on a linked list "gcc -o qsort qsort.c"

qsort.c

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

typedef struct List {
  int n;
  void *next;
} List;

List* ListNew (int n) {
  List *l = malloc(sizeof(List));
  l->next = NULL;
  l->n    = n;
  return l;
}

List* ListAdd (List *l, int n) {
  List *ln = ListNew(n);
  ln->next = l;
  return ln;
}

void ListPrint (List *l) {
  if (l->next) {
    printf("%d,",l->n);
    ListPrint(l->next);
  } else {
    printf("%d\n", l->n);
  }
}

List* ListLessThan (List *l, int n) {
  List *nl = NULL;
  while (1) {
    if (l->n < n) {
      nl = nl ? ListAdd(nl, l->n) : ListNew(l->n);
    }
    l = l->next;
    if (!l) break;
  }
  return nl;
}

List* ListGreaterEqual (List *l, int n) {
  List *nl = NULL;
  while (1) {
    if (l->n >= n) {
      nl = nl ? ListAdd(nl, l->n) : ListNew(l->n);
    }
    l = l->next;
    if (!l) break;
  }
  return nl;
}

List* ListConcat (List *h, List *t) {
  List *temp = h;
  while (1) {
    if (temp->next) {
      temp = temp->next;
    } else {
      temp->next = t;
      break;
    }
  }
  return h;
}

List* qsort (List *l) {
  if (!l->next) return l;
  List *temp;
  List *lt = ListLessThan(l->next, l->n);
  List *ge = ListGreaterEqual(l->next, l->n);
  l->next = NULL;
  if (lt) {
    temp = ListConcat(qsort(lt), l);
  } else {
    temp = l;
  }

  if (ge)
    temp = ListConcat(temp, qsort(ge));

  return temp;
}

int main () {
  List *l1 = ListNew(5);
  List *l2 = ListAdd(l1, 5);
  List *l3 = ListAdd(l2, 4);
  List *l4 = ListAdd(l3, 3);
  List *l5 = ListAdd(l4, -1);
  List *l6 = ListAdd(l5, 2);
  List *l7 = ListAdd(l6, 1);
  List *l8 = ListAdd(l7, 1);
  ListPrint(l8);
  ListPrint(qsort(l8));
  return 0;
}