Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

segregate
even
odd
linked list
data structures

How to segregate even and odd numbers in a linked list

Educative Answers Team

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(){
    // Declaring the linked list:
    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
linked list
data structures
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring