# 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.

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;
}else{
//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){
}
while(temp!=NULL){
printf("%d  ",temp->data);
temp=temp->next;
}
}
// segregate even and odd element of linked list

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

printf("\nBefore segregate :");
printf("\nAfter  segregate :");
}``````

#### 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;
};
public:
void insert(int);
void display();
void segregate();
};
}

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

//separates nodes
while(temp!=NULL){
hold=temp;
temp=temp->next;
if(hold->data%2==0){
//gets even nodes
}else{
//gets odd nodes
hold->next=odd;
odd=hold;
}
}
//even node are exist
while(temp->next!=NULL){
temp=temp->next;
}
//add Remaining odd nodes
temp->next=odd;
}else{
//when only odd nodes
}
}
}
int main(){
//create object
//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 {

//Class constructors
}
//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 {
}
}
// segregate even and odd element of linked list
public void segregate() {

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

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

public static void main(String[] args) {

//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

def __init__(self):
#Assign default value

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

def display(self):
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) :

hold=None
odd=None

#separates nodes
while(temp!=None):
hold=temp
temp=temp.next
if(hold.data%2==0):
#gets even nodes
else:
#gets odd nodes
hold.next=odd
odd=hold

#even node are exist
while(temp.next!=None):
temp=temp.next
#add Remaining odd nodes
temp.next=odd
else:
#when only odd nodes

def main():
#Create Object of class Linked
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
{
public Program(){
}
//insert node of linked list
public void insert(int data){
Node newNode=new Node();
newNode.data=data;
newNode.next=null;
else{
//get last node
while(temp.next!=null){
temp=temp.next;
}
temp.next=newNode;
}
}
//display linked list nodes value
public void display(){
Console.Write("Empty List");
}else{
while(temp!=null){
Console.Write("  {0}",temp.data);
temp=temp.next;
}

}
}
void segregate(){

Node temp=head, hold=null, odd=null;

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

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

function __construct()
{
}
/*
* Append the Given data value at end of linked list
* Fun : insert
* Parm: data value
*@return None
*/
function insert(\$data)
{
\$newNode=new Node(\$data);
{
}else{
//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(){

\$hold=NULL;
\$odd=NULL;

//separates nodes
while(\$temp!=NULL){
\$hold=\$temp;
\$temp=\$temp->next;
if(\$hold->data%2==0){
//gets even nodes
}else{
//gets odd nodes
\$hold->next=\$odd;
\$odd=\$hold;
}
}
//even node are exist
while(\$temp->next!=NULL){
\$temp=\$temp->next;
}
//add Remaining odd nodes
\$temp->next=\$odd;
}else{
//when only odd nodes
}
}
}
//Display all inserted node in linked list
function display()
{
{
echo "Empty Linked List";
}
else
{
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

/*
*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.