Table of contents
1.
Introduction 
1.1.
Problem Statement
1.2.
Explanation of the problem 
1.3.
Sample Example 
2.
Brute Force Approach  
2.1.
Steps of the Approach
2.2.
Implementation in C++ 
2.3.
Complexity Analysis
3.
Optimized Approach  
3.1.
Steps of the Algorithm
3.2.
Implementation in C++ 
3.3.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a Linked List?
4.2.
What is Time Complexity?
4.3.
What is Space Complexity?
5.
Conclusion
Last Updated: Mar 27, 2024

Alternate Odd and Even Nodes in a Singly Linked List

Author Vidhi Singh
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction 

Linked List is one of the most important data structures when it comes to technical interviews. It helps the interviewer test the candidate’s knowledge of pointers and problem-solving skills. 

This article will discuss the problem: Alternate Odd and Even Nodes in Linked List 

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm

Problem Statement

Given a Singly Linked List with nodes having integer values. Your task is to arrange the nodes of the Singly Linked List such that alternate nodes have even and odd values. The number of nodes with even and odd values is equal.  

Also read - Merge sort in linked list

Explanation of the problem 

In the question, there is a Singly Linked List with nodes that store integer values. You are supposed to think of a function that arranges the nodes such that the alternate nodes have even values.  

Sample Example 

If the given Linked List is: 

Then after alternating even and odd nodes, it would be as follows: 

 

Brute Force Approach  

So, the first way to do so can that keep nodes with odd values at the odd position and ones with even values at the even position. For instance, in the above-mentioned example, odd valued nodes are at 1st, 3rd, and 5th positions while even valued are at 2nd, 4th, and 6th positions respectively after rearrangement.

We traverse the Linked List from the start, nodes that are in their right positions, are left untouched. But for nodes that are not in their appropriate positions, there is a different strategy. 

Odd values nodes that are not in their correct positions, will be stored at one place and even valued at another. Now, taking one node from each of the two groups they can be exchanged. Two stacks are used to store even and odd nodes differently. 

For instance, taking the above example.  

Step1:

 

 Step 2:

 

 

 Step 3:

Step 4: 

 

Step 5: 

 

Step 6:

 

Step 7: 

 

In the considered example, there was only one element in each of the stacks, if there is more than one, then nodes are popped from both of them and their values are exchanged till both the stacks get empty. 

One thing to observe here is that number of elements in both the stacks will always be equal because if one node is at the wrong position, the other one will also have to be at the wrong position.  

Steps of the Approach

  1. Initialize two stacks and start traversing the given Linked List 
  2. Check the value of the node 
  3. If the value of the node is even and it is present at the odd position then push it into the Even Stack. Similarly, if the value of the node is odd and it is present at the even position then push it into the Odd Stack. 
  4. Repeat steps 3 and 4 till the end of the Linked List is not encountered. 
  5. Exchange the values of the top nodes of the Odd Stack and Even Stack. 
  6. Pop the top node from both the stack. 
  7. Repeat steps 5 and 6 till boht the stacks are not empty. 

Implementation in C++ 

#include<bits/stdc++.h>
using namespace std;

class Node      //Node of the Linked List
{
    public:
        int value;
        Node* next;
};
 
void print(Node* head)      //Printing the Linked List
{
    Node *t=head; 
    while(t!=NULL) 
    {
        cout<<t->value<<" ";
        t=t->next;
    }
    cout<<endl;
}

Node* new_node(int num)
{
    Node* t=new Node;
    t->value=num;
    t->next=NULL;
    return t;
}
 
Node* insert(Node* head, int num)  //Inserting node in the Linked List
{
    Node* t=new_node(num);
    if(head==NULL) 
    {
        head=t;  
        return head;
    }
    Node *s=head; 
    while(s->next!=NULL) 
        s=s->next; 
    s->next=t;
    return head;
}
 
void Odd_Even(Node* head)       //Alternating even and odd nodes
{
    stack<Node*> odd;
    stack<Node*> even;
    int pos=1;
 
    while (head!=NULL) 
    {
 
        if(head->value%2!=0 && pos%2==0) 
        {
            odd.push(head);
        }
        else if(head->value%2==0 && pos%2!=0) 
        {
            even.push(head);
        }
        head=head->next;
        pos++;
    }
    while (!odd.empty()&&!even.empty()) 
    {
 
        swap(even.top()->value,odd.top()->value);
        even.pop();
        odd.pop();
    }
}
 
int main()
{ 
	Node* head=new_node(5);
	head=insert(head,6);
	head=insert(head,12);
	head=insert(head,11);
	head=insert(head,1);
	head=insert(head,18);
   	
	cout<<"Linked List before re arrangement: ";
	print(head);
	Odd_Even(head);
 	
	cout<<"Linked List after re arrangement: ";
	print(head);
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output:

Linked List before re arrangement: 5 6 12 11 1 18 
Linked List after re arrangement: 5 6 11 12 1 18 

Complexity Analysis

Time Complexity: O(n)

Here, ‘n’ is the count of nodes in the Linked List. Since all the nodes of the Linked List are traversed once and if there are nodes in the stack, then also it gives linear complexity.  

In the worst case, all the nodes night be there in the stack, but then also, they are accessed once from there, making no change in the Linked List. 

 

Space Complexity: O(n) 

We only need space for them in the stack, which is linear. 

Optimized Approach  

As you can see the above approach already has linear time complexity and in order to make nodes alternate in the specified manner we need to access all of them at least once. This brings us to the conclusion that time complexity cannot be reduced from linear. 
But, that approach uses linear space as well. Let us think of reducing this. 

To reduce space, we can go like this. 

Keep all the odd value nodes together and even valued together in the Linked List itself. Then alternate those nodes. 
For this, we can bring odd valued nodes at the start of the Linked List and even valued towards the end. After segregation of the nodes like this, we can bring one even after odd. 

Let us go through the steps of the algorithm, that will make it more clear. 

Steps of the Algorithm

  1. Check the node value.
    → if the node value is odd, bring it to the start of the Linked List.
    → If the node value is even, bring it to the end of the Linked List.
  2. Repeat step 1 for every node of the Linked List. 
  3. Keep a pointer to the first even valued node and another to the first odd valued node in the Linked List. 
  4. Bring the even valued node after the odd valued node. 
  5. Move both the pointers to the next even valued node and odd valued node respectively. 
  6. Repeat steps 4 and 5 till the end of the Linked List. 

Implementation in C++ 

#include <bits/stdc++.h>
using namespace std;
 
class Node     //Node of the Linked List 
{
    public:
        int value;
        Node* next;
};
 
void print(Node* head)      //Printing Linked List
{
    while(head!=NULL) 
    {
        cout<<head->value<<" ";
        head=head->next;
    }
    cout<<endl;
}
 
Node* new_node(int num)      //Creating new node for Linked List
{
    Node* t= new Node;
    t->value=num;
    t->next=NULL;
    return t;
}
 
Node* insert(Node* head,int num)  //Inserting nodes in the Linked List
{
    Node* t= new_node(num);
    t->next=head;
    head=t;
    return head;
}
 
void Odd_Even(Node** head)     //Alteing even and odd nodes
{
    Node* even;
    Node *t,*pt;
    Node *i,*j,*k,*l,*pr;
 
    t=(*head)->next;
    pt=*head;
 
    while(t!=NULL)
    {
 
        Node* x=t->next;
        if(t->value% 2!=0)
        {
            pt->next=x;
            t->next=(*head);
            (*head)=t;
        }
        else 
        {
            pt=t;
        }
        t= x;
    }
 
    t=(*head)->next;
    pt=(*head);
 
    while(t!=NULL && t->value%2!=0) 
    {
        pt=t;
        t=t->next;
    }
    even=t;
    pt->next=NULL;
    i=*head;
    j=even;
 
    while(j!=NULL && i!=NULL) 
    {
        k=i->next;
        l=j->next;
        i->next=j;
        j->next=k;
        pr=j;
        i=k;
        j=l;
    }
    
    if(i==NULL) 
    {
        pr->next=j;
    }
}
 
int main()
{
	Node * head = new_node(18);
	head = insert(head, 1);
	head = insert(head, 11);
	head = insert(head, 12);
	head = insert(head, 6);
	head = insert(head, 5);
	cout << "Linked List before re arrangement: ";
	print(head);
	cout << "Rearranged List after re arrangement: ";
	Odd_Even( & head);
	print(head);
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output:

Linked List before re arrangement: 5 6 12 11 1 18 
Rearranged List after re arrangement: 1 6 11 12 5 18 

Complexity Analysis

Time Complexity: O(n)

Here, ‘n’ is the count of nodes in the Linked List. Since all the nodes of the Linked List are accessed twice, it is linear.
 

Space Complexity: O(1) 

We are taking constant extra space, so it takes constant space complexity. 

Frequently Asked Questions

What is a Linked List?

A Linked List is a data structure that is basically a collection of nodes that contain some data and pointers to the other node(s). 

What is Time Complexity?

Time complexity in Computer Science is the amount of time taken by an algorithm to execute. It is expressed as a function of the amount of input.

What is Space Complexity?

Space Complexity in Computer Science for an algorithm is the total space used by the algorithm based on its input size. It includes both auxiliary space and input space. 

Conclusion

This article extensively discusses the programming problem: Alternate Odd and Even Nodes in a Singly Linked List along with their pseudocode, implementation, and time trade-offs

We hope that this blog has helped you enhance your knowledge regarding Alternating Odd and Even Nodes in a Singly Linked List, and if you would like to learn more, check out our articles on Coding Ninjas Blogs

You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSQLSystem Design, and many more!
If you want to test your competency in coding, you may check out the Mock Test Series and participate in the Contests organized on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the Problems, Interview Experiences, and Interview Bundle for placement preparations.

Nevertheless, you may consider our Courses to give your career an edge over others!

Do upvote our blog to help other ninjas grow. 

Happy Learning!

Live masterclass