Given a Linked List of integers, write a function to modify the linked list such that all even numbers appear before all the odd numbers in the modified linked list. Also, keep the order of even and odd numbers same. - (from geeksforgeeks: Segregate even and odd nodes in a Linked List)
Example:
Input:
3 7 17 15 8 9 2 4 6 4 1 3 5 7 7 8 12 10 5 4 1 6
Output:
8 2 4 6 17 15 9 1 3 5 7 8 12 10 4 6 5 1
My Approach: get pointer to the last node of list. And then traverse the list starting from the head node and move the odd valued nodes from their current position to end of the list.Also if all the node's data is even or odd then list remains unmodified so first I check if this is the case then I simply return(len is total number of nodes & count is total number of even data nodes).
I am getting right answer on an IDE, but on other IDE where the code needs to be submitted, it's showing time limit exceeded.
How do I optimize my code?
#include <iostream>
using namespace std;
int flag=0;
struct Node{
int data;
Node* next;
};
void addkey(struct Node** head_ref,int key)
{struct Node* temp=(struct Node*)malloc(sizeof(Node));
temp->next=NULL;
temp->data=key;
if(*head_ref==NULL)
{
*head_ref=temp;
}
else
{
struct Node* ptr=*head_ref;
while(ptr->next!=NULL)
{
ptr=ptr->next;
}
ptr->next=temp;
}
}
void segregate(struct Node**head_ref)
{ int len=0,count=0;
struct Node* ptr1=*head_ref;
struct Node* ptr2=*head_ref;
struct Node* prev=NULL;
while(ptr2->next!=NULL)
{
if((ptr2->data)%2==0) count++;
ptr2=ptr2->next;
len++;
}
if(ptr2->data%2==0) count++;
if(count==len+1||count==0) return;
struct Node* ptr5=ptr2;
while(ptr1!=ptr5->next)
{
if((ptr1->data%2)==0)
{ if(flag==0) {
*head_ref=ptr1;
flag=1;}
prev=ptr1;
ptr1=ptr1->next;
}
else
{
if(prev!=NULL) prev->next=ptr1->next;
ptr2->next=ptr1;
ptr2=ptr2->next;
ptr1=ptr1->next;
ptr2->next=NULL;
}
}
}
void printlist(struct Node* head)
{
if(head==NULL) return;
else
{
while(head!=NULL)
{
cout<<head->data<<" ";
head=head->next;
}
}
}
int main() {
int T ;
cin>>T;
while(T--)
{
int n;
cin>>n;
struct Node* head=(struct Node*)malloc(sizeof(Node));
head=NULL;
for(int i=0;i<n;i++)
{int key;
cin>>key;
addkey(&head,key);
}
segregate(&head);
printlist(head);cout<<"\n";
}
return 0;
}