Segregate even and odd nodes in a Linked List

Suppose that given of linked list is combination of integers element. And we are need to separate this linked list nodes in the form of Even and Odd Nodes. Arrange all Even key Nodes at beginning, After that arranging Odd Key Nodes.

For example inserted the following (1,2,3,4,5,6,7,8,10) node in a sequence.

Before segregate even and odd node After segregate even and odd node

Implementation approach: Use two pointers variables, let say that is p1 and p2 , and assign those pointer value to NULL. make new pointer p3 that are used to traversal of linked list node. check that p3 node value is Even Key or not.

Even then add this element at front of p1, otherwise add this element to front of p2.(when p1 is NULL then assign first Even Node reference to p1 pointer, similarly when p2 is NULL then set first odd node reference to p2 pointer).

When p3 is NULL that means, p1 is contains the Even Value linked list nodes. And p2 is combination of Odd Value nodes. append p1 last node next pointer is to p2. And set head pointer value to p1.

Test cases: Before write an algorithm consider following test cases.

1) When linked list are empty then display valid message (like empty linked list).

2) There is possible linked list is combination of similar type of elements like All Even key or all Odd key. for example.

Case 1: (all Even key nodes)
Linked List : 1->3->5->7-9->NULL
After Segregate: 1->3->5->7-9->NULL (not modified element)

Case 2: (all Odd key nodes)
Linked List : 2->4->6->8->NULL
After Segregate:  2->4->6->8->NULL (not modified element)

In this situation are not modified the original linked list.

Here given code implementation process.

//C Program 
//Segregate even and odd nodes in linked list
#include<stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node{
  int data;
  struct Node*next;
};
//function prototype
void insert(struct Node**,int);
void display(struct Node*);
void segregate(struct Node**);
//insert Node element
void insert(struct Node**head,int value){
  //Create dynamic node
  struct Node*node=(struct Node*)malloc(sizeof(struct Node));
  if(node==NULL){
    printf("Memory overflow\n");
  }else{
    node->data=value;
    node->next=NULL;
    if(*head==NULL){
      *head=node;
    }else{
      struct Node*temp=*head;
      //find last node
      while(temp->next!=NULL){
        temp=temp->next;
      }
      //add node at last possition
      temp->next=node;
    }
  }
}
//Display element of Node
void display(struct Node*temp){
  
  if(temp==NULL){
    printf("Empty linked list");
  }
  while(temp!=NULL){
    printf("%d  ",temp->data);
    temp=temp->next;
  }
}
// segregate even and odd element of linked list
void segregate(struct Node**head){

  if(*head!=NULL){
    struct Node*temp=*head,*hold=NULL,*odd=NULL;
    *head=NULL;

    //separates nodes
    while(temp!=NULL){
      hold=temp;
      temp=temp->next;
      if(hold->data%2==0){
        //gets even nodes
        hold->next=*head;
        *head=hold;
      }else{
        //gets odd nodes
        hold->next=odd;
        odd=hold;
      }
    }
    if(*head!=NULL){
      //even node are exist
      temp=*head;
      while(temp->next!=NULL){
        temp=temp->next;
      }
      //add Remaining odd nodes
      temp->next=odd;
    }else{
      //when only odd nodes
       *head=odd;
    }
  }
}
int main(){
  //create node pointer
  struct Node*head=NULL;
  //insert element of linked list

  insert(&head,1);
  insert(&head,2);
  insert(&head,3);
  insert(&head,4);
  insert(&head,5);
  insert(&head,6);
  insert(&head,7);
  insert(&head,8);
  insert(&head,10);
  printf("\nBefore segregate :");
  display(head);
  printf("\nAfter  segregate :");
  segregate(&head);
  display(head);
}

Output

Before segregate :1  2  3  4  5  6  7  8  10  
After  segregate :10  8  6  4  2  7  5  3  1
//C++ Program
//Segregate even and odd nodes in a Linked List
#include<iostream>
using namespace std;

//create structure
struct Node{
  int data;
  struct Node*next;
};
class LinkedList{
  Node *head;
  public:
    LinkedList();
    void insert(int);
    void display();
    void segregate();
};
LinkedList::LinkedList(){
  head=NULL;
}

//insert Node element
void LinkedList::insert(int value){
    //Create dynamic nodes
  struct Node*node=new Node;
  if(node==NULL){
    cout<<"Memory overflow\n";
  }else{
    node->data=value;
    node->next=NULL;
    if(head==NULL){
      //base condition
      head=node;
    }else{
      Node*temp=head;
      while(temp->next!=NULL){
        temp=temp->next;
      }
      //add newly node at last
      temp->next=node;
    }
  }
}
//display element of Node
void LinkedList:: display(){
  Node*temp=head;
  if(temp==NULL){
    cout<<"Empty linked list";
  }
  while(temp!=NULL){
    cout<<temp->data<<" ";
    temp=temp->next;
  }
}
// segregate even and odd element of linked list
void LinkedList:: segregate(){

  if(head!=NULL){
    Node*temp=head,*hold=NULL,*odd=NULL;
    head=NULL;

    //separates nodes
    while(temp!=NULL){
      hold=temp;
      temp=temp->next;
      if(hold->data%2==0){
        //gets even nodes
        hold->next=head;
        head=hold;
      }else{
        //gets odd nodes
        hold->next=odd;
        odd=hold;
      }
    }
    if(head!=NULL){
      //even node are exist
      temp=head;
      while(temp->next!=NULL){
        temp=temp->next;
      }
      //add Remaining odd nodes
      temp->next=odd;
    }else{
      //when only odd nodes
       head=odd;
    }
  }
}
int main(){
  //create object
  LinkedList obj;
  //insert element of linked list
  obj.insert(1);
  obj.insert(2);
  obj.insert(3);
  obj.insert(4);
  obj.insert(5);
  obj.insert(6);
  obj.insert(7);
  obj.insert(8);
  obj.insert(10);
  cout<<" Before Segregate :";
  obj.display();
  obj.segregate();
  cout<<"\n After  Segregate :";
  obj.display();
}

Output

 Before Segregate :1 2 3 4 5 6 7 8 10 
 After  Segregate :10 8 6 4 2 7 5 3 1
//Java program 
//Segregate even and odd nodes in linked list
class Node {
  public int data;
  public Node next;
  public Node(int value) {
    data = value;
    next = null;
  }
}

public class LinkedList {

  public Node head;
  //Class constructors
  LinkedList() {
    head = null;
  }
  //insert Queue element
  public void insert(int value) {
    //Create Queue node
    Node node = new Node(value);

    if (head == null) head = node;
    else {
      Node temp = head;
      //find last node
      while (temp.next != null) {
        temp = temp.next;
      }
      temp.next = node;
    }

  }
  //Display all Linked List elements
  public void display() {
    if (head != null) {

      Node temp = head;
      while (temp != null) {
        System.out.print("  " + temp.data);
        temp = temp.next;
      }
    } else {
      System.out.println("Empty Linked list");
    }
  }
  // segregate even and odd element of linked list
  public void segregate() {

    if (head != null) {
      Node temp = head, hold = null, odd = null;
      head = null;

      //separates nodes
      while (temp != null) {
        hold = temp;
        temp = temp.next;
        if (hold.data % 2 == 0) {
          //gets even nodes
          hold.next = head;
          head = hold;
        } else {
          //gets odd nodes
          hold.next = odd;
          odd = hold;
        }
      }
      if (head != null) {
        //even node are exist
        temp = head;
        while (temp.next != null) {
          temp = temp.next;
        }
        //add Remaining odd nodes
        temp.next = odd;
      } else {
        //when only odd nodes
        head = odd;
      }
    }
  }

  public static void main(String[] args) {

    LinkedList obj = new LinkedList();
    //insert element of linked list
    obj.insert(1);
    obj.insert(2);
    obj.insert(3);
    obj.insert(4);
    obj.insert(5);
    obj.insert(6);
    obj.insert(7);
    obj.insert(8);
    obj.insert(10);

    System.out.print(" Before Segregate :");
    obj.display();
    obj.segregate();

    System.out.print("\n After  Segregate :");
    obj.display();
  }
}

Output

 Before Segregate :  1  2  3  4  5  6  7  8  10
 After  Segregate :  10  8  6  4  2  7  5  3  1
#Python Program
#Segregate even and odd nodes in linked list
class Node:
    def __init__(self,data):
        self.data=data
        self.next=None

#Create Class Linked    
class Linked:
    def __init__(self):
        #Assign default value
        self.head=None

    #insert new node to linked list  
    def insert(self,data):
        node=Node(data)
        node.next=None
        if self.head==None:
            self.head=node
        else:
            temp=self.head
            while temp.next!=None:
                temp=temp.next
            #add node    
            temp.next=node

    def display(self):
        temp=self.head
        print("Linked List Elements : "),
        while(temp!=None):
          print(temp.data),
          temp=temp.next
        print("\n")

    #segregate even and odd element of linked list 
    def segregate(self) :

      if(self.head!=None):
        temp=self.head
        hold=None
        odd=None
        self.head=None

        #separates nodes
        while(temp!=None):
          hold=temp
          temp=temp.next
          if(hold.data%2==0):
            #gets even nodes
            hold.next=self.head
            self.head=hold
          else:
            #gets odd nodes
            hold.next=odd
            odd=hold
        
        if(self.head!=None):
            #even node are exist
            temp=self.head
            while(temp.next!=None):
                temp=temp.next
            #add Remaining odd nodes
            temp.next=odd
        else:
            #when only odd nodes
            self.head=odd




def main():
    #Create Object of class Linked
    obj=Linked()
    #Perform Linked operation
    obj.insert(1)
    obj.insert(2)
    obj.insert(3)
    obj.insert(4)
    obj.insert(5)
    obj.insert(6)
    obj.insert(7)
    obj.insert(8)
    obj.insert(10)
    print("Before segregate")
    obj.display()
    obj.segregate()
    print("After segregate")
    obj.display()
if __name__=="__main__":
    main()

Output

Before segregate
Linked List Elements :  1 2 3 4 5 6 7 8 10 

After segregate
Linked List Elements :  10 8 6 4 2 7 5 3 1 
//C# Program
//Segregate even and odd nodes in linked list
using System;
//node class
public class Node{
 public  int data;
 public  Node next;
}
class Program
{
  Node head;
  public Program(){
    head=null;
  }
    //insert node of linked list
  public void insert(int data){
    Node newNode=new Node();
    newNode.data=data;
    newNode.next=null;
    if(head==null) head=newNode;
    else{
      Node temp=head;
            //get last node
      while(temp.next!=null){
        temp=temp.next;
      }
            //add new node
      temp.next=newNode;
    }
  }
    //display linked list nodes value
  public void display(){
    if(head==null){
      Console.Write("Empty List");
    }else{
      Node temp=head;
      while(temp!=null){
        Console.Write("  {0}",temp.data);
        temp=temp.next;
      }

    }
  }
  void segregate(){

    if(head!=null){
      Node temp=head, hold=null, odd=null;
      head=null;

      //separates nodes
      while(temp!=null){
        hold=temp;
        temp=temp.next;
        if(hold.data%2==0){
         //gets even nodes
          hold.next=head;
          head=hold;
        }else{
        //gets odd nodes
          hold.next=odd;
          odd=hold;
        }
      }
      if(head!=null){
        //even node are exist
        temp=head;
        while(temp.next!=null){
          temp=temp.next;
        }
        //add Remaining odd nodes
        temp.next=odd;
      }else{
        //when only odd nodes
        head=odd;
      }
    }
  }

  static void Main()
  {
    Program obj=new Program();
    obj.insert(1);
    obj.insert(2);
    obj.insert(3);
    obj.insert(4);
    obj.insert(5);
    obj.insert(6);
    obj.insert(7);
    obj.insert(8);
    obj.insert(10);

    Console.Write(" Before Segregate :");
    obj.display();
    obj.segregate();
   
    Console.Write("\n After  Segregate :");
    obj.display();
  }
}

Output

Before Segregate :  1  2  3  4  5  6  7  8  10
 After  Segregate :  10  8  6  4  2  7  5  3  1
<?php
//Php program 
//Segregate even and odd nodes in a Linked List
class Node
{
    public $data;
    public $next;
    function __construct($data)
    {
        $this->data = $data;
        $this->next = NULL;
    }
}
class LinkedList{

    public $head;
    function __construct()
    {
        $head=NULL;
    }
       /*
    * Append the Given data value at end of linked list
    * Fun : insert
    * Parm: data value
    *@return None
    */
    function insert($data)
    {
        $newNode=new Node($data); 
        if($this->head==NULL)
        {
            $this->head=$newNode;
        }else{
            $temp=$this->head;
            //find last node of linked list
            while($temp->next!=NULL){
                $temp=$temp->next;
            }
            //add new node to last of linked list
            $temp->next=$newNode;
        }
    }
    // segregate even and odd element of linked list
    function segregate(){

      if($this->head!=NULL){
        $temp=$this->head;
        $hold=NULL;
        $odd=NULL;
        $this->head=NULL;

        //separates nodes
        while($temp!=NULL){
          $hold=$temp;
          $temp=$temp->next;
          if($hold->data%2==0){
            //gets even nodes
            $hold->next=$this->head;
            $this->head=$hold;
          }else{
            //gets odd nodes
            $hold->next=$odd;
            $odd=$hold;
          }
        }
        if($this->head!=NULL){
          //even node are exist
          $temp=$this->head;
          while($temp->next!=NULL){
            $temp=$temp->next;
          }
          //add Remaining odd nodes
          $temp->next=$odd;
        }else{
          //when only odd nodes
           $this->head=$odd;
        }
      }
    }
    //Display all inserted node in linked list
    function display()
    {
        if($this->head==NULL)
        {
            echo "Empty Linked List";
        }
        else
        {
            $temp=$this->head;
            echo "<br>Linked List :";
            while($temp!=NULL)
            {
                //display node value
                echo "&nbsp;&nbsp;".$temp->data;
                $temp=$temp->next; //visit to next node
            }
        }   
    }
}
function main(){
  //Make a object of LinkedList class
  $obj= new LinkedList();

  /*
  *Insert following nodes in linked list
  */
 
  $obj->insert(1);
  $obj->insert(2);
  $obj->insert(3);
  $obj->insert(4);
  $obj->insert(5);
  $obj->insert(6);
  $obj->insert(7);
  $obj->insert(8);
  $obj->insert(10);
  echo " Before Segregate :";
  $obj->display();
  $obj->segregate();
  echo "<br> After  Segregate :";
  $obj->display();
}
main();
?>

Output

Before Segregate :
Linked List :  1  2  3  4  5  6  7  8  10
After Segregate :
Linked List :  10  8  6  4  2  7  5  3  1

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved