Segregate even and odd nodes in a Linked List C++

In this tutorial, we will see how to segregate even and odd nodes in a linked list in C++.

Segregate even and odd nodes mean, given a linked consisting of even and odd nodes, arrange the nodes in such a way that in the modified list all even numbers should appear before all odd numbers, and their order should be preserved.

Example:

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6
Output: 2 -> 4 -> 6 -> 1 -> 2 -> 3

C++ program to segregate even and odd nodes in a Linked List

To do so we will follow a simple technique, that is we will break the linked list into two different linked lists one which only contains odd nodes and one which contagion even nodes.
After doing this we just have to concatenate both the string to get the desired output string.

Below the implementation shows how the following can be achieved.

IMPLEMENTATION

Approach:

1. Remove all even nodes from the linked list (it will have only odd nodes after this).
2. Use the removed nodes to construct a new linked list (it will have only even nodes).
   (It can be done both with and without using extra space)
3. Join these two linked lists to get the final linked list.

Code:

#include <bits/stdc++.h>
using namespace std;

//node structure
typedef struct node
{
    int data;
    struct node *next;
} node;

//creates a linked list
node *createList(node *head, int n)
{
    node *newnode, *temp = head;
    for (int i = 0; i < n; i++)
    {
        //allocating space for new node
        newnode = (node *)malloc(sizeof(node));

        //it checks whether space is allocated or not
        if (!newnode)
            return head;

        //inputting value of the new node
        cin >> newnode->data;

        /*initially each new node will be the last node
        in the linked list until a new node arrives*/
        newnode->next = NULL;

        //if the new node is the first node in the linked list
        if (head == NULL)
        {
            head = newnode;
            temp = head;
        }

        /*if there are nodes already present in the linked list
        then the new node will be placed after the last node*/
        else
        {
            temp->next = newnode;
            temp = newnode;
        }
    }
    return head;
}

//display a linked list
//iterate from the head node till we get NULL
void display(node *head)
{
    node *temp = head;
    while (temp != NULL)
    {
        if (temp->next == NULL)
            cout << temp->data;
        else
        {
            cout << temp->data;
            cout << " -> ";
        }
        temp = temp->next;
    }
}

node *segregate(node *head1)
{
    node *temp1 = head1;

    //head2 will be used to access all evev elements
    node *head2 = NULL;
    node *temp2 = head2;

    /*this will remove all the even nodes present in the beginning
    of the linked list and will use them to form a different
    linked list consisting of only even elements*/
    while (head1 != NULL && (head1->data) % 2 == 0)
    {
        if (head2 == NULL)
        {
            head2 = head1;
            temp2 = head2;
        }
        else
        {
            temp2->next = head1;
            temp2 = temp2->next;
        }
        head1 = head1->next;
        temp2->next = NULL;
    }

    temp1 = head1;

    /*this will remove all even nodes present in between
    and end of the linked list*/
    while (temp1 != NULL && temp1->next != NULL)
    {
        if ((temp1->next->data) % 2 == 0)
        {
            if (head2 == NULL)
            {
                head2 = temp1->next;
                temp1->next = temp1->next->next;
                temp2 = head2;
            }
            else
            {
                temp2->next = temp1->next;
                temp1->next = temp1->next->next;
                temp2 = temp2->next;
            }
            temp2->next = NULL;
        }
        else
            temp1 = temp1->next;
    }
    
    /*this condition exectues if all elements in the linked
    list are odd*/
    if (head2 == NULL)
        return head1;
    else
    {
        temp2->next = head1;
        return head2;
    }
}

int main()
{
    /*head pointer will be used to access elements in
    the linked list*/
    node *head = NULL;

    int n;
    cout << "Enter the size of the linked list: ";
    cin >> n;
    cout << "Enter elements in the linked list: ";
    head = createList(head, n);
    cout << "Original linked list: ";
    display(head);
    head = segregate(head);
    cout << "\nSegregated linked list: ";
    display(head);
    return 0;
}

Output:

Enter the size of the linked list: 6
Enter elements in the linked list: 1 2 3 4 5 6
Original linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6  
Segregated linked list: 2 -> 4 -> 6 -> 1 -> 3 -> 5

Time Complexity: O(n)
Space Complexity: O(1)
where,
n -> size of the linked list