Segregate Even and Odd Nodes in a Linked List

Segregate Even and Odd Nodes in a Linked List” is one of the favourite technical interview problem based on linked list asked in many technical interviews of product based companies. 

Here, we are given a linked list and our task is to segregate even and odd nodes in a linked list. We need to modify the given linked list in such a way that all odd nodes of linked list appear before the even nodes.

Note: The sequence of odd and even number nodes should not be changed.

For example, we need to segregate even and odd nodes of a following linked list:
LINKED LIST:       12 -> 13 -> 14 -> 15 -> 16 -> 17
After segregating the nodes,
LINKED LIST:       13 -> 15 -> 17 -> 12 -> 14 -> 16

The steps required to segregate even and odd nodes in a linked list are as follows:

  1. If linked list is empty or contains only one element, then return.
  2. Initialize two new lists: odd_list and even_list with NULL, which will contain odd nodes and even nodes of a linked list, respectively.
  3. Traverse complete linked list and one by one check whether current node value is odd number or even number. If the node value is odd number, then remove it and add it to odd_list. Similarly, if the node value is even number, then remove it and add it to even_list. 
  4. Now, traverse the odd_list and attach the last node to the head of the even_list.
  5. Change head of the odd_list to original head of the linked list.

C++ Program to segregate even and odd nodes in a linked list is as follows:

/* C++ Program to segregate even and odd nodes in a linked list */
#include<bits/stdc++.h>
using namespace std;

/* structure of the node of the linked list */
typedef struct node
{
    int data;
    struct node *next;
}Node;

/* Function to Insert node at the end of the linked list */
void insert_end(Node **head, int ele)
{
    /* Creating a new node */
    Node *new_node;
    new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = ele;
    new_node->next = NULL;
    
    /* check whether the linked list is empty or not */
    
    /* If Linked List is empty, new node will become head of the linked list */
    if(*head == NULL)     
    {
        *head = new_node;
        return;
    }
    
    /* If linked list is not empty, traverse the complete linked list and point the pointer of
       last node of the linked list to the new node */
    Node *temp = NULL;
    temp = (*head);
    while(temp->next != NULL)
    temp=temp->next;
    temp->next = new_node;
}
/* Function to Segregate Even and Odd Nodes of the Linked List */
void segregateEvenOddNodes(Node **head)
{
    /* If Linked List is empty or contains only one node, then simply return. */
    if((*head) == NULL || (*head)->next == NULL)
    return;
    
    /* Initialize 4 node pointers pointing to beginning and end of two new linked list:
    odd list and even list.
    oddStart - points to the start of the odd node list.
    oddEnd - points to the end of the even node list.
    evenStart - points to the start of the even node list.
    evenEnd - points to the end of the even node List
    */
    Node *oddStart = NULL;
    Node *evenStart = NULL;
    Node *oddEnd = NULL;
    Node *evenEnd = NULL;
    
    Node *temp = (*head);
    Node *p = NULL;
    /*
        Traverse the complete linked list and one by one check whether node value is even or node.
        If Node value is odd, remove the node from the list and attach it to the odd list. Similarly,
        If Node value is even, remove the node from the list and attach it to the even list.
    */
    while(temp != NULL)
    {
        if(temp -> data %2 == 0)
        {
            p = temp;
            temp = temp -> next;
            p -> next = NULL;
            if(evenStart == NULL)
            {
                evenStart = p;
                evenEnd = evenStart;
            }
            else
            {
                evenEnd -> next = p;
                evenEnd = evenEnd -> next;
            }
        }
        else
        {
            p = temp;
            temp = temp -> next;
            p -> next = NULL;
            if(oddStart == NULL)
            {
                oddStart = p;
                oddEnd = oddStart;
            }
            else
            {
                oddEnd -> next = p;
                oddEnd = oddEnd -> next;
            }
        }
    }
    /* If there are no even nodes in the list, then head will be oddstart */
    if(evenStart == NULL)
    {
        *head = oddStart;
    }
    /* Else if there are no odd nodes in the list, then head will be evenstart */
    else if(oddStart == NULL)
    {
        *head = evenStart;
    }
    /* If both even and odd node list exists, then attach the last node of the odd list to the 
    beginning of the even list */
    else
    {
        oddEnd -> next = evenStart;
        *head = oddStart;
    }
    
}

/* Function to Print the Linked List */    
void print(Node *head)
{
    Node *temp = head;
    while(temp!=NULL)
    {
        cout<<temp->data<<" ";
        temp=temp->next;
    }
    cout<<endl;
}


int main()
{
    Node *head = NULL;
    /* Inserting Some Nodes in the Linked List */
    insert_end(&head,12);
    insert_end(&head,13);
    insert_end(&head,14);
    insert_end(&head,15);
    insert_end(&head,16);
    insert_end(&head,17);
    cout<<"The Linked List before segregating is:\n";
    print(head);
    segregateEvenOddNodes(&head);
    cout<<"\nThe Linked List after segregating is:\n";
    print(head);
}
OUTPUT:
The Linked List before segregating is:
12 13 14 15 16 17
The Linked List after segregating is:
13 15 17 12 14 16

Related Posts:

  1. Insert a New Node at the Sorted Linked List.
  2. Reverse a Linked List.
  3. Reverse a Linked List Using Stack.
  4. Printing Linked List in Reverse Order without actually reversing the Linked List.
  5. Swap Adjacent Elements of the Linked List.
  6. Count All Occurrences of a Particular Node in a Linked List.
  7. Bubble Sort on Linked List.
  8. Detect a Loop in a Linked List.
  9. Find the Length of the Loop present in the Linked List.
  10. Detect and Remove Loop from a Linked List.
  11. Delete Complete Linked List.
  12. Delete Nth Node of the Linked List.
  13. Delete without head pointer of the Linked List.
  14. Delete All Occurrences of particular node of the Linked List.
  15. Delete Alternate Nodes of the Linked List.
  16. Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
  17. Remove Duplicate Nodes from an Unsorted Linked List.
  18. Remove Duplicate Nodes from a Sorted Linked List.
  19. Find Union and Intersection of Two Linked List.
  20. Merge Two Sorted Linked List.

You may also like...