Segregate Even and Odd Nodes in a Linked List

A linked list is a linear data structure in which each node has two blocks. One contains the node’s value or data, and the other includes the address of the next field.

Let us assume that we have given a linked list such that each node contains the data and a pointer that is pointing to the next node of the linked list. The task is to Segregate the given Linked List. Segregating the linked list means we have to separate the odd indexed nodes and even index nodes in the list.

For Example:

Input :

 1-> 2-> 4-> 7-> 9-> 11-> NULL

Output:

1-> 4-> 9 -> 2-> 7-> 11 -> NULL

Explanation: The given linked list after separating each odd index nodes and even indexed terms the linked list will be,

                      1-> 4-> 9 -> 2-> 7-> 11 ->NULL

Approach to solve this Problem:

We will introduce three-pointers for the odd index, even index, and even index value to segregate the given linked list. After that, we will iterate over the whole linked list and initialize the pointer with some value. The indexing starts from ‘1’; thus, the plan’s first node will always be treated as an odd indexed node for any particular string. However, the next of it is treated as an even indexed node.

Take Input of a linked list with data and pointer to the next node.
A function segregateList(listnode *head) takes the pointer to the head node and returns the segregated linked list as output.
Initialize three-pointers oddIndex, even index, and evenHead, which are currently pointing to the list’s head.
Iterate over the whole linked list and initialize the next pointer of the odd index with the next pointer of even index.
Now iterate over the whole list and initialize the next pointer of even index with the odd index’s next pointer.
Return the head pointer.

C++ code:

#include <iostream> using namespace std; 
class node{                    
 public:    
 int data;  
 node*next;     
 node(int d){                    data=d;         next=NULL;              }
 }; 
 node* segregateList(node* head)
 {        
 if(head==NULL)
{            
 return NULL;        
 }        
 node*oddIndex= head;       
  node*evenIndex= head->next;      
   node*evenHead=evenIndex;     
    while(evenIndex!=NULL and evenIndex->next!=NULL)
{            
 oddIndex->next= evenIndex->next;    
         oddIndex=oddIndex->next;      
       evenIndex->next= oddIndex->next;      
       evenIndex= evenIndex->next;       
  }     
    oddIndex->next= evenHead; 
        return head;   
  } 
 void insertAtNode(node*&head, int data)
{      
 node*n= new node(data);     
  n->next= head;            
     head=n;              
     }
 void print(node*head)
{    
 while(head!=NULL)
{           
 cout<<head->data<<"->";     
  head= head->next;        
    } 
} 
int main() 
{     
node*head=NULL;   // It could be possible that the head node contains NULL Value.     
insertAtNode(head,5);     
insertAtNode(head,8);     
insertAtNode(head,3);     
insertAtNode(head,1);     
insertAtNode(head,2);     
print(head);     cout<<endl;    
 segregateList(head);    
 print(head); 
}

Running the above code will generate the following output:

Output:

 2 ->1 ->3 ->8 ->5 ->
 2 ->3 ->5 ->1 ->8 ->

Segregate the given Linked List in DAA