Segregate even and odd nodes in a linked list

For the given input linked list, write a function to segregate all even and all odd such that all even appear before all odd. We should keep the order of even and odd unchanged.

Example

Time complexity : O(n)

Algorithm

1. Traverse the linked list and get the pointer to the last node.

2. Move all the odd nodes to the end in the same order.

a. Move all odd nodes before the first even and move them to end.
b. Change the head pointer to point to the first node.
c.  Move all the odd nodes after the first node and move them to the end.Do this by storing previous pointer and detach it and add it at the end and update current and previous.

C++ Program

#include <bits/stdc++.h>

using namespace std;

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

/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
    struct LLNode* current = new LLNode;
    current->data = dataToBeInserted;
    current->next = NULL;    
    if(*head == NULL)
            *head=current; //If this is first node make this as head of list
        
    else
        {
            current->next=*head; //else make the current (new) node's next point to head and make this new node a the head
            *head=current;
        }
        
        //O(1) constant time
}
 
//display linked list
void display(struct LLNode**node)
{
    struct LLNode *temp= *node;
    while(temp!=NULL)
        {
            if(temp->next!=NULL)
            cout<<temp->data<<"->";
            else
            cout<<temp->data;
            
            temp=temp->next; //move to next node
        }
        //O(number of nodes)
    cout<<endl;
}
 
void Segregate(struct LLNode **head)
{
    struct LLNode *end = *head;
    struct LLNode *previous = NULL;
    struct LLNode *current = *head;
    //get the pointer to the last node
    while (end->next != NULL)
    {
        end = end->next;
    }
    struct LLNode *new_end = end;
    //Move all odd nodes before first even to the end
    while(current->data % 2 != 0 && current != end)
    {
        new_end->next = current;
        current = current->next;
        new_end->next->next = NULL;
        new_end = new_end->next;
    }
 
    //Change head to the first even node
    if(current->data%2 == 0)
    {
        //current points to first even
        *head = current;
        while(current!= end)
        {
            //If found even move forward and store previous
            if((current->data)%2 == 0)
            {
                previous = current;
                current = current->next;
            }
            //detach the odd and add it in the end
            //update end
            else
            {
                previous->next = current->next;
                current->next = NULL;
                new_end->next = current;
                new_end = current;
                current = previous->next;
            }
        }
    }
    else previous = current;
    //If till end there is no even then make next of end to null
    if (new_end!=end && (end->data)%2 != 0)
    {
        previous->next = end->next;
        end->next = NULL;
        new_end->next = end;
    }
    return;
}

//Main function 
int main()
{
    //Initial LL has no nodes
    struct LLNode* head = NULL;
    insertAtBeginning(&head, 9);
    insertAtBeginning(&head, 4);
    insertAtBeginning(&head, 6);
    insertAtBeginning(&head, 7);
    insertAtBeginning(&head, 12);
    insertAtBeginning(&head, 11);
    insertAtBeginning(&head, 8);
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 1);

    cout<<"Input linked list:    ";
    display(&head);
 
    Segregate(&head);
 
    cout<<"Modified linked list: ";
    display(&head);
 
    return 0;
}

 

Translate »