w3.q20

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
struct Node
{
    int data;
    Node *next;
    Node (int x)
    {
        data=x;
        next=NULL;
    }
};
void segevenodd(Node *head);
void printList(struct Node *head)
{
    struct Node* temp=head;
    while(temp!=NULL)
    {
        cout<<temp->data<<" ";
        temp=temp->next;
    }
}
int main()
{
    int T,n,l,f;
    cin>>T;
    while(T--)
    {
        struct Node *head=NULL,*tail=NULL;
        cin>>n>>f;
        head =new Node(f);
        tail=head;
        for(int i=1;i<n;i++)
        {
            cin>>l;
            tail->next=new Node(l);
            tail=tail->next;
        }
        segevenodd(head);
        printList(head);
        cout<<endl;
    }
    return 0;
}
void segevenodd(Node* head)
{
    Node *q=head;
    Node *p=head;
    Node *prev=NULL;
    while(q && q->next)
    {
        q=q->next;
    }
    Node *temp=q;
    while(p!=temp && p->data%2!=0)
    {
        q->next=p;
        p=p->next;
        q->next->next=NULL;
        q=q->next;
    }
    if(p->data%2==0)
    {
        head=p;
        while (p != temp)  
        {  
            if ( (p->data) % 2 == 0 )  
            {  
                prev = p;  
                p= p->next;  
            }  
            else
            {  
                prev->next = p->next;  
                p->next = NULL;  
                q->next = p;  
                q =p ;  
                p = prev->next;  
            }  
        }  
    }  
    else prev = p;  
    if (q != temp && (temp->data) % 2 != 0)  
    {  
        prev->next = temp->next;  
        temp->next = NULL;  
        q->next = temp;  
    }  
    return;  
}