#include<stdio.h>
#include<stdlib.h>
typedef struct linkedlist
{
	int data;
	struct linkedlist *next;
} Node;

Node *makeNewNode(int data)
{
	Node *new = (Node*) malloc(sizeof(Node));
	new->data = data;
	new->next = NULL;
	return new;
}

Node *insert_after_cur(Node *cur, int data)
{
	Node *new = makeNewNode(data);
	if(cur == NULL) cur = new;
	else if(cur->next == NULL) cur->next = new;
	else{
        new->next=cur->next;
        cur->next=new;
	}
    cur = new;
	return cur;
}

void split(Node *head, Node **L1, Node **L2)
{
	Node *cur, *cur1, *cur2;
	cur = head;
	cur1=NULL;
	cur2=NULL;
	while(cur!=NULL){
		if((cur->data)%2!=0){
			if((*L1)==NULL){
				cur1 = cur;
				*L1 = cur1;
			}
			else {
                cur1->next=cur;
                cur1 = cur;
			}
		}
		else{
			if((*L2)==NULL){
				cur2 = cur;
				*L2 = cur2;
			}
			else {
                cur2->next=cur;
                cur2 = cur;
			}
		}
		cur=cur->next;
	}
	if(cur1 != NULL) cur1->next = NULL;
	if(cur2 != NULL) cur2->next = NULL;
}

int main()
{
	Node *L, *cur;
	Node **L1, **L2;
	int i;

	L = NULL;
    L1 = malloc(sizeof(Node*));
    L2 = malloc(sizeof(Node*));
	*L1 = NULL;
	*L2 = NULL;

    cur = L;
	L = insert_after_cur(cur,0);
	cur = L;
	for(i=1; i<20; i++){
		cur = insert_after_cur(cur,i);
	}
	split(L,L1,L2);


	Node *tempnode = (*L1);
	while(tempnode!=NULL)
	{
		printf("%d\n",tempnode->data);
		tempnode = tempnode->next;
	}

	tempnode = (*L2);
	while(tempnode!=NULL){
		printf("%d\n", tempnode->data);
		tempnode = tempnode->next;
	}
	return 0;

}