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;

{
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)

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

then the new node will be placed after the last node*/
else
{
temp->next = newnode;
temp = newnode;
}
}
}

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

{

//head2 will be used to access all evev elements

/*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*/
{
{
}
else
{
temp2 = temp2->next;
}
temp2->next = NULL;
}

/*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)
{
{
temp1->next = temp1->next->next;
}
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*/
else
{
}
}

int main()
{
/*head pointer will be used to access elements in

int n;
cout << "Enter the size of the linked list: ";
cin >> n;
cout << "Enter elements in the linked list: ";
cout << "Original linked list: ";
cout << "\nSegregated linked list: ";
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