# 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:**

- Remove all even nodes from the linked list (it will have only odd nodes after this).
- 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) - 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

## Leave a Reply