Linked List: Segregate even and odd nodes in a Linked List

Problem Statement:

You are given an LL, you need to segregate the list such that all the even number appear before all the odd numbers in the modified list.

Example

Input:  1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> NULL
Output: 2 -> 4 -> 6 -> 8 -> 1 -> 3 -> 5 -> 7 -> 9 -> NULL

Solution

In this solution we split the LL into two. One containing all even nodes and other containing all odd nodes.

Then we attach the odd node after even node LL.

Here we are not taking separate LL, but we are considering two dummy nodes, that will maintain two pointers that will point to the last node in individual lst.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <stack> 

using namespace std;

struct Node 
{
    int data;
    struct Node* next;
};

void insert_at_begenning ( struct Node **head_pointer, int data)
{
    // allocate memory for new node
    struct Node *temp_node = (struct Node*) malloc(sizeof(struct Node));

    // assign the data to new node
    temp_node->data = data;

    // initialize the new node to point to NULL
    temp_node->next = NULL;

    // if this is the first pointer, then this is the head pointer
    if (*head_pointer == NULL)
    {
        *head_pointer = temp_node;
    }
    else
    {
        // point the next of the present pointer to the head pointer
        temp_node->next = *head_pointer;

        //then move the reference of head pointer to the current pointer
        *head_pointer = temp_node;
    }
}

void display_list(struct Node **head_pointer)
{
    // take a reference to head pointer for navigation
    struct Node *temp = *head_pointer;

    while(temp != NULL)
    {
        if(temp->next != NULL)
            printf("%d -> ", temp->data);
        else
            printf("%d", temp->data);

        //navigate to next pointer
        temp = temp->next;
    }
    printf("\n");
}

void segregate_even_odd(struct Node **head_ref) 
{ 
    // starting node of list having even values. 
    Node *evenStart = NULL; 
      
    // ending node of even values list. 
    Node *evenEnd = NULL; 
      
    // starting node of odd values list. 
    Node *oddStart = NULL; 
      
    // ending node of odd values list. 
    Node *oddEnd = NULL; 
      
    // node to traverse the list. 
    Node *currNode = *head_ref; 
      
    while(currNode != NULL)
    { 
        int val = currNode -> data; 
          
        if(val % 2 == 0) 
        { 
            if(evenStart == NULL)
            { 
                evenStart = currNode; 
                evenEnd = evenStart; 
            }  
            else
            { 
                evenEnd -> next = currNode; 
                evenEnd = evenEnd -> next; 
            } 
        }  
          
        else
        { 
            if(oddStart == NULL)
            { 
                oddStart = currNode; 
                oddEnd = oddStart; 
            } 
            else
            { 
                oddEnd -> next = currNode; 
                oddEnd = oddEnd -> next; 
            } 
        } 
                      
        currNode = currNode -> next;     
    } 
      
    if(oddStart == NULL || evenStart == NULL)
    { 
        return; 
    } 
      
    evenEnd -> next = oddStart; 
    oddEnd -> next = NULL; 
      
    *head_ref = evenStart; 
} 
  

   int main()
{
    struct Node *list_1 = NULL; 

    insert_at_begenning(&list_1,1);
    insert_at_begenning(&list_1,2);
    insert_at_begenning(&list_1,3);
    insert_at_begenning(&list_1,4);
    insert_at_begenning(&list_1,5);
    insert_at_begenning(&list_1,6);
    insert_at_begenning(&list_1,7);

    printf("Original List:\n");
    display_list(&list_1);

    segregate_even_odd (&list_1);
 
    printf("\nAfter Segregate List:\n");
    display_list(&list_1);

    return 0;
}

Output:

Original List:
7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1

After Segregate List:
6 -> 4 -> 2 -> 7 -> 5 -> 3 -> 1