Related Tags

segregate
even
odd
data structures

# How to segregate even and odd numbers in a linked list

To segregate even and odd numbers in a linked list is to manipulate them so that all of the even numbers come before all of the odd numbers â€‹while still preserving their respective orders.

## Algorithm

The following algorithm segregates a linked list:

1. Start iterating from the first element:

(a) If the number is odd, remove it and place it at the end of the list.

(b) If the number is even, do nothing.

2. Go to the next element.

3. If the last element of the original list has been reached, stop. Oâ€‹therwise, repeat steps 1-2.

Odd number found
1 of 12

## C++ code

The <list> container has been used in the code below:

#include <iostream>
#include <list>

using namespace std;

void printList(list<int>* n){
for(int i : *n)
cout << i << ", ";

cout << endl;
}

int main(){
list<int> numbers {1, 4, 21, 3, 6, 2, 9, 7};

// Declaring iterator for the Linked List:
list<int>::iterator ptr = numbers.begin();;

// Print original array:
cout << "Original Array: ";
printList(&numbers);

// Applying algorithm:
int s = (int)numbers.size();
int i = 0;

while(i < s){
if((*ptr) % 2 != 0){
numbers.push_back(*ptr);
ptr = numbers.erase(ptr);
i++;
}
else{
ptr++;
i++;
}
}

// Printing resultant array:
cout << "Segregated array: ";
printList(&numbers);

return 0;
}


RELATED TAGS

segregate
even
odd