## 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

- Initialize two stacks and start traversing the given Linked List
- Check the value of the node
- 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.
- Repeat steps 3 and 4 till the end of the Linked List is not encountered.
- Exchange the values of the top nodes of the Odd Stack and Even Stack.
- Pop the top node from both the stack.
- 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;
}
```

**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.