/*
* Definition for linked list.
* class Node {
* public:
* int data;
* Node *next;
* Node() : data(0), next(nullptr) {};
* Node(int x) : data(x), next(nullptr) {}
* Node(int x, Node *next) : data(x), next(next) {}
* };
*/
void insertAtEnd(Node* &tail,int data){
Node* newNode=new Node(data);
tail->next=newNode;
tail=newNode;
}
Node* segregateEvenOdd(Node* head)
{
// Write your code here
Node* evenHead=new Node(-1);
Node* evenTail=evenHead;
Node* oddHead=new Node(-1);
Node* oddTail=oddHead;
Node* temp=head;
while(temp){
if(temp->data %2==0){
insertAtEnd(evenTail,temp->data);
}
else{
insertAtEnd(oddTail,temp->data);
}
temp=temp->next;
}
evenHead=evenHead->next;
evenTail->next=oddHead->next;
return evenHead;
}