## Introduction

A linked list is a linear data structure where elements are not stored contiguously but randomly. They are instrumental in implementing stacks and queues, graphs, performing arithmetic operations on large integers, and representing sparse matrices.

It is a vital topic from the placement point of view, and there are several problems related to it.

This blog will discuss one such significant problem, rearranging a linked list such that all even and oddly positioned nodes are together.

Also see Data Structures

## Problem Statement

You have been provided with the head pointer of a singly linked list. Your task is to rearrange the elements of the linked list such that all the nodes at the even positions occur together and all the nodes at the odd positions occur together. Let us look at a few examples to get a clear understanding.

**Example:**

- Input:
**1→2→3→4→5**

Output:** 1→3→5→2→4**

- Input:
**2→1→3→5→6→4→7**

Output:** 2→3→6→7→1→5→4**

### Algorithm

Before solving the problem, one thing that should be kept in mind is the different cases possible in the linked list:

- No nodes
- One node
- Two nodes
- Odd number of nodes
- Even the number of nodes

So, keeping in mind all the above cases, we can design the following algorithm:

- Maintain 2 pointers ‘
’ and ‘**ODD**’ for the node at the odd and even positions, respectively.**EVEN** - Traverse the original linked list and put the odd nodes in the odd linked list and the even nodes in the even linked list.
- Also, store the first node of the even linked list so that the even linked list can be attached at the end of the odd list after all the odd and even nodes have been connected in different lists.

__INITIAL STEP:__

__STEP 1:__

__STEP 2:__

__STEP 3:__

### Implementation

```
// C++ program to rearrange a linked list such that all even and odd positioned nodes are together.
#include <iostream>
using namespace std;
// 'NODE' class to store linked list nodes.
class Node
{
public:
int data;
Node *next;
// Constructor to create a node with given data.
Node(int data)
{
this->data = data;
next = NULL;
}
};
// 'LINKED_LIST' class to create linked list objects.
class LinkedList
{
// 'HEAD' pointer to store the address of the first node.
Node *head;
public:
LinkedList()
{
head = NULL;
}
// Function to print the linked list elements.
void printLinkedList()
{
/*
'CURRENT' node pointer traverses through the linked list.
Set 'CURRENT' node equal to the first node of the linked list.
*/
Node *current = head;
// Loop to traverse the linked list.
while (current)
{
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
// Function to insert nodes in the linked list.
void insert(int data)
{
/* If linked list is empty, create a new node
and direct the 'HEAD' node to the newly created node.
*/
if (head == NULL)
{
head = new Node(data);
return;
}
// Else traverse the linked list until the end of the list is encountered.
Node *current = head;
while (current->next)
{
current = current->next;
}
// Create and insert a new node at the end of the linked list.
current->next = new Node(data);
}
// Function to rearrange a linked list such that all even and odd positioned nodes are together.
void rearrangeEvenOdd()
{
if (head == NULL)
return;
// Initialising the first nodes of even and odd lists.
Node *odd = head;
Node *even = head->next;
// Storing the first node of the linked list so that it can be connected at the end of the odd list.
Node *evenFirst = even;
while (1)
{
// If the odd list and the even lists have ended, the first node of the even linked list is connected to the last node of the odd linked list.
if (!odd || !even || !(even->next))
{
odd->next = evenFirst;
break;
}
// Connecting the odd nodes.
odd->next = even->next;
odd = even->next;
// If there are no more even nodes after the current odd node.
if (odd->next == NULL)
{
even->next = NULL;
odd->next = evenFirst;
break;
}
// Connecting the even nodes.
even->next = odd->next;
even = odd->next;
}
}
};
int main()
{
int n;
// Taking user input.
cout << "Enter the size of the linked list: ";
cin >> n;
cout << "Enter the values of the nodes: ";
LinkedList *givenList = new LinkedList();
for (int i = 0; i < n; i++)
{
int data;
cin >> data;
givenList->insert(data);
}
// Calling the function to rearrange the linked list such that all even and odd positioned nodes are together.
givenList->rearrangeEvenOdd();
// Printing this modified linked list.
cout << "The modified linked list is: ";
givenList->printLinkedList();
return 0;
}
```

Input

```
Enter the size of the linked list: 5
Enter the values of the nodes:
1 2 3 4 5
```

Output

```
The modified linked list is:
1 3 5 2 4
```

### Complexity Analysis

**Time Complexity**

**O(N)**, where **N** is the size of the linked list.

Since we are traversing the entire linked list with **N** nodes only once, the time complexity is given by **O(N).**

**Space Complexity**

The space complexity is **O(1)**.

The space complexity is constant as we are not using extra space except for variables and pointers.

Recommended Topic, __Floyds Algorithm__