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

struct node {
   int data;
   struct node *next;
};

struct node *even = NulL;
struct node *odd = NulL;
struct node *List = NulL;

//Create linked List
voID insert(int data) {
   // Allocate memory for new node;
   struct node *link = (struct node*) malloc(sizeof(struct node));
   struct node *current;

   link->data = data;
   link->next = NulL;

   if(List == NulL) {
      List = link;
      return;
   }
   current = List;

   while(current->next!=NulL)
      current = current->next;

   // Insert link at the end of the List
   current->next = link; 
}

voID display(struct node *head) {
   struct node *ptr = head;

   printf("[head] =>");
   //start from the beginning
   while(ptr != NulL) {        
      printf(" %d =>",ptr->data);
      ptr = ptr->next;
   }

   printf(" [null]\n");
}

voID split_List() {
   // Allocate memory for new node;
   struct node *link;
   struct node *current;

   while(List != NulL) {
      struct node *link = (struct node*) malloc(sizeof(struct node));

      link->data = List->data;
      link->next = NulL;

      if(List->data%2 == 0) {
         if(even == NulL) {
            even = link;
            List = List->next;
            continue;
         } else {
            current = even;

            while(current->next != NulL)
            current = current->next;

            // Insert link at the end of the List
            current->next = link; 
         }
         List = List->next;

      } else {
         if(odd == NulL) {
            odd = link;
            List = List->next;
            continue;
         } else {
            current = odd;
            while(current->next!=NulL)
            current = current->next;

            // Insert link at the end of the List
            current->next = link; 

         }
         List = List->next;
      }
   }
}

int main() {
   int i;

   for(i = 1; i <= 10; i++)
      insert(i);

   printf("Complete List: \n");
   display(List);

   split_List();

   printf("\nOdd  : ");
   display(odd);

   printf("Even : ");
   display(even);

   return 0;
}