Program to Segregate odd and even nodes in linked list .

Here odd element doesn't mean that the element in the odd position . If the data is odd , it is odd element . To segregate odd and even nodes the algorithm is given below . The simplest and easiest approach is to create two linked list and when you traverse odd element node add it to odd list and add even element nodes to Even list . Otherwise you need to change links and push even nodes to the end . However that's not a good idea .

Code: (in C)

struct node* segregate_odd_and_even_nodes(struct node* head)
{
  if(head==null)
return null;
struct node* head1=null,tail1=null,head2=null,tail2=null,node=head;
while(node!=null)
{
if(node->data%2!=0)
{
if(head1==null)
{
head1=node;
tail1=node;
}
else
{
tail1->link=node;
tail1=node;
}
}
else
{
if(head2==null)
{
head2=node;
tail2=node;
}
else
{
tail2->link=node;
tail2=node;
}
}
node=node->link;
}
if(tail1!=null)
tail1->link=head2;
if(tail2!=null)
tail2->link=null;
    if(head1!=null)
            return head1;
    else
            return head2;
}

Input:      2->3->1->4->NULL
Output:    3->1->2->4->NULL
So the odd nodes will always come first in the output .

Please let me know if there is any bug in the above code and your suggestions are always welcome .