Linked List: Odd Even Linked List

Problem Statement:

Given a singly LL group all odd nodes together followed by the even nodes.

We need the node number not the value in the node.

Example

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

Solution

Solution is very simple.

As we need to group the node numbers together.

Take 2 pointers, odd will point to the first node.

even will point to the next node of the each nodes.

At the end connect the odd node hext to even node head

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");
}

Node* odd_even_list(Node* head) 
{

    if(head == NULL || head->next == NULL)
        return head;

    Node *odd = head;
    Node *even_head = head->next;
    Node *even = even_head;
    
    while(even != NULL && even->next != NULL)
    {
        odd->next = even->next;
        odd = odd->next;
        even->next = odd->next;
        even = even->next;
    }
    odd->next = even_head;
    return head;
}
  

   int main()
{
    struct Node *list_1 = NULL; 
    struct Node *result = 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);

    result = odd_even_list (list_1);
 
    printf("\nAfter Segregate List:\n");
    display_list(&result);

    return 0;
}

Output:

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

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