struct Node
{
	int data;
	struct Node* next;

	Node(int x){
		data = x;
		next = NULL;
	}
};

Node* divide(int N, Node *head){
    // code here
    
    Node *evenHead=NULL,*oddHead=NULL;
    Node *even=NULL,*odd=NULL,*t=head;
    
    while(t!=NULL)
    {
        if (t->data%2 == 0)
        {
            if (evenHead == NULL)
            {
                evenHead = t;
                even=t;
            }
            else
            {
                even->next=t;
                even=even->next;
            }
        }
        else
        {
            if (oddHead == NULL)
            {
                oddHead = t;
                odd=t;
            }
            else
            {
                odd->next=t;
                odd=odd->next;
            }
        }
        
        t=t->next;
    }
    
    if (even) even->next=oddHead;
    
    if (odd) odd->next=NULL;
    
    if (evenHead) return evenHead;
    
    return oddHead;
    
}