### Problem Statement

In this problem, we will be given a linked list, and we need to rearrange the nodes such that the nodes present at odd positions and the nodes present at even positions are together.

### Problem Statement Understanding

To understand this problem statement, let us take examples.

If the given linked list is:

then according to the problem statement:

- Starting the counting from 1, the nodes at odd positions are 3,18, and 5.
- Nodes at even positions are 1 and 12.
- So, after rearrangement, the resultant list will be:

Let us take another example:

If the linked list is 4â†’1â†’10â†’42â†’5â†’NULL.

- Starting the counting from 1, the nodes at odd positions are 4,10, and 5.
- Nodes at even positions are 1 and 42.
- So, after rearrangement, the resultant list will be 4â†’10â†’5â†’1â†’42â†’NULL.

Now, I think the problem statement is clear, so let's see how we can approach it. Any ideas?

- If not, it's okay; we will see in the next section how we can approach it.

Letâ€™s move to the approach section.

### Approach

- We will use two pointers, where at first, we will initialize these pointers with the address of the first and the second node of the linked list.
- Now, we will iterate the list from the first node to the last node.
- While iterating, we will connect the node pointed by each pointer to the node next to the adjacent node in its right.
- This will ensure that all odd and even positioned nodes are with each other, respectively.

- At last, we need to connect the tail of the odd list with the head of the even list.
- Finally, after all the above steps, we will have our rearranged linked list with all the even and the odd positioned nodes together.

The approach is discussed in more depth in the algorithm section.

### Algorithm

1) We will return NULL if the head is NULL, i.e., the input list is empty.

2) Initialize two pointers **odd** and **even** with the first and the second node of the list, respectively.

3) Initialize a pointer **evenHead** with the second node.

4) Run an infinite while loop and inside it:

- If any one of
**odd**,**even**, or**evenâ†’next**is NULL (i.e., we have reached the end of the list, so we will connect the last node of odd list to the first node of the even list), then attach the tail of**odd**to the head of**even**and break from the loop. - Connect
**odd**to the node next to**even**and update**odd**with this node. - If the node next to
**odd**is NULL (i.e., no node after the current odd node), then update the next of**even**as NULL and attach the tail of**odd**to the head of**even**and break from the loop. - Connect
**even**to the node next to**odd**and update**even**with this node.

5) Return**head**at last from the function.

### Dry Run

### Code Implementation

#includeusing namespace std; class Node{ public: int data; Node* next; Node(int x){ data = x; next = NULL; } }; // Using this function we will print the linked list void printList(Node *head) { if (!head) return; while (head->next != NULL) { cout << head->data << ","; head = head->next; } cout << head->data << endl; } // Function to rearrange the linked list Node *rearrangeEvenOdd(Node *head) { // Empty list condition if (head == NULL) return NULL; Node *odd = head; Node *even = head->next; // first node of even list Node *evenHead = even; while (1) { // If we have reached end of the list // then, connect last node of odd list // to the first node of even list if (!odd || !even || !(even->next)) { odd->next = evenHead; break; } odd->next = even->next; odd = even->next; // No nodes after current odd node if (odd->next == NULL) { even->next = NULL; odd->next = evenHead; break; } even->next = odd->next; even = odd->next; } return head; } int main(void){ Node* head = NULL; head = new Node(3); head->next = new Node(1); head->next->next = new Node(18); head->next->next->next = new Node(12); head->next->next->next->next = new Node(5); cout<<"Original linked list without rearrangement: "<

#### Output

Original linked list without rearrangement:

3,1,18,12,5

Linked list after rearrangement:

3,18,5,1,12

**Time Complexity:** O(n), where n is the total number of nodes in the list

So, in this blog, we have tried to explain how we can rearrange a linked list such that all even and odd positioned nodes are together most optimally. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.