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;
}

Find the Immediate Ancestor of a node

There are two ways by which we can find the immediate ancestor of the node . One way is same like Lowest Common Ancestor Problem . The other way is suggested by my friend ,that's almost the same idea . But the style of coding is different . I really liked the second Method .

1st Method:(in C)

struct node * immediateAncestor(struct node *root,struct node *node)
{
if(root==NULL)
return NULL;
if(root->left==node || root->right==node)
return root;
else
{
struct node* left,right;
left=immediateAncestor(root->left,node);
right=immediateAncestor(root->right,node);
return (left!=NULL)?left:right;
}
}

2nd Method:(in C++)

node* ancestor(node *root, node *x)
{
if(root == NULL || x==NULL || root == x)
return NULL;
if(root->left==x || root->right==x)
return root;
return (ancestor(root->left,x)||ancestor(root->right,x));
}

Swap alternate nodes in a singly linked list

The concept is very easy . But you need to handle all test cases. One of the important test case is before assigning the odd_node->link to even_node , you should check whether it is NULL or NOT . Otherwise it will cause Segmentation Fault .

Code:

struct node* swap_alternate_nodes(struct node* head)
{
struct node* odd_node,even_node,temp;
if(head==NULL)
return NULL;
odd_node=head;
even_node=head->link;
if(head->link!=NULL)
head=head->link;
while(odd_node && even_node)
{
temp=even_node->link;
even_node->link=odd_node;
odd_node->link=temp;
              odd_node=temp;
if(odd_node!=NULL)
even_node=odd_node->link;
}
return head;
}

Input :   1->2->3->4->5->NULL
Output: 2->1->4->3->->5->NULL