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

#define LIST_SIZE 100

typedef struct _node {
   int element;
   struct _node *next;
} node;

node *createList ( int n )
{
   int i;
   node *L, *p;

   p = L = (node *)malloc(sizeof(node));
   for (i=0; i<n; ++i) {
      p -> next = (node *)malloc(sizeof(node));
      p = p -> next;
      p -> element = rand() % 1000;
   }
   p -> next = NULL;
   return L;
}

void printList ( node *L )
{
   node *p;
   int cnt;

   p = L -> next; cnt = 0;
   while (p != NULL) {
      printf("%4d", p -> element);
      p = p -> next;
      if (++cnt % 20 == 16) printf("\n");
   }
   printf("\nNumber of elements = %d\n", cnt);
}

void splitList ( node *L , node *L1 , node *L2 )
{
   node *p, *p1, *p2;
   int pivot;

   p = L -> next;
   pivot = p -> element;
   p1 = L1;
   p2 = L2;
   while (p != NULL) {
      if ((p -> element) <= pivot) { 
         p1 -> next = p;
         p1 = p1 -> next;
      } else {
         p2 -> next = p;
         p2 = p2 -> next;
      }
      p = p -> next;
   }
   p1 -> next = NULL;
   p2 -> next = NULL;
}

int main ()
{
   node *L, *L1, *L2;

   srand((unsigned int)time(NULL));
   L = createList(LIST_SIZE);
   printf("\nOriginal list : "); printList(L);
   L1 = (node *)malloc(sizeof(node));
   L2 = (node *)malloc(sizeof(node));
   splitList(L,L1,L2);
   printf("\nSublist 1     : "); printList(L1);
   printf("\nSublist 2     : "); printList(L2);
}