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 .

Simple C Program to Find Loop in the Linked List

This is a famous question asked in many interviews . And you probably know the answer . The Idea to solve this problem is to use two pointers, where one pointers moves by one pointer and another pointer moves by two pointers . The general idea is if two people are running in  a circle if one person is running at 1x speed and another one is running at 2x speed they will meet after 2 rounds(person who is running at 1x speed will complete one round where other one completes 2 rounds ).

Code : (in C)
int detect_loop(struct node * head)
{
if(head==null && head->link==null)
return 0;
struct node* first,second;
first=head;
second=head->link;
while(first!=second)
{
first=first->link;
if(second->link==null || second->link->link==null)
return 0;
second=second->link->link;
}
if(first==second) // found the loop
return 1;
return 0;
}

if the function returns 0 that means there is no loop , otherwise there is a loop in the linked list .

please let me know if there is any bug in the above code.

Copy the linked list which has the random pointer and it points to any node in linked list .

The solution is to use copy-merge-split . First copy the nodes and create a new list . Then merge the nodes into the original list .Assume that ur original list is 1->2->3->NULL and u have copied the list and merged it into the orginal list . so the list will look like this 1->1->2->2->3->3->NULL . Then for the random pointer , the even nodes random pointer should point to the odd node's random->next pointer . Then separate the odd and even nodes .

Code is given below . Please let me know if there is any mistake in the code .

Code :(in C)
The node structure is given below .
struct node
{
int data;
struct node* next;
struct node* random;
}

struct node* copy_list_with_random_pointer(struct node * head)
{
//copy list and don't worry about random pointer now
struct node* copied_list_head=copy_list(head);
if(copied_list_head==NULL)
return NULL;
//merge the copied list into original list
struct node* original_list,copied_list,temp,temp1;
original_list=head;
copied_list=copied_list;
while(original_list!=NULL)
{
temp=original_list;
original_list=original_list->link;
temp->link=copied_list;

temp1=copied_list;
copied_list=copied_list->link;
temp1->link=original_list;
}

//set the random pointer for copied list
temp=head;
while(temp!=NULL)
{
temp->link->random=temp->random->next;
temp=temp->link->link;
}
 
       //split the list
original_list=head;
copied_list=head->link;
while(original_list!=null)
{
original_list->link=copied_list->link;
original_list=copied_list->link;
if(original_list!=NULL)
{
copied_list->link=original_list->link;
copied_list=original_list->link;
}
else
copied_list->link=NULL;

}

return copied_list_head;
}

//function to copy the the linked list
struct node* copy_list(struct node * head)
{
if(head==NULL)
return NULL;
struct node* temp,new_head=NULL,tail=NULL;
temp=head;
while(temp!=NULL)
{
struct node* node=malloc(sizeof(struct node*));
if(new_head==NULL)
new_head=node;
if(tail!=NULL)
tail->link=node;

               tail=node;

node->data=temp->data;
temp=temp->link;
}
tail->link=null;
return new_head;
}