# Rearrange a linked list such that all even and odd positioned nodes are together

__Introduction__

__Introduction__

A * linked list* is a linear data structure where elements are not stored contiguously but randomly. They are instrumental in implementing

*and*

__stacks__*,*

__queues__*, performing arithmetic operations on large integers, and representing sparse matrices.*

__graphs__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, to rearrange a linked list such that all even and odd positioned nodes are together.

__Problem Statement__

__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:__

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

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

__Implementation__**Program**

**Program**

```
// 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__

__Input__

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

__Output__

__Output__

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

**Time Complexity**

**Time Complexity**

* O(N)*, where

*is the size of the linked list.*

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

**O(N).****Space Complexity**

**Space Complexity**

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

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

__Key Takeaways__

__Key Takeaways__

So, this blog discussed how to rearrange a linked list such that all even and odd positioned nodes are together. To learn more, head over right now to* ** CodeStudio* to practice problems on topics like

__Linked List__*,*

__Graphs__*,*

*and crack your interviews like a Ninja!*

__Trees__Practicing a bunch of questions is not enough in this competitive world. So go check out where you stand among your peers by taking our __mock tests__* *and see which areas need improvement.

In case of any comments or suggestions, feel free to post them in the comments section.

Comments

## No comments yet

## Be the first to share what you think