**Introduction**

Are you not able to shuffle and manipulate the pointers in a linked list? Or if you can solve all questions on linked lists? In either case, we have brought you another problem on linked lists, i.e., rearrange a linked list in place. We will help you approach this problem using illustrations, intuition, and some code in the C++ programming language, which will make the problem easier for you to understand.

Source: __Link__

The question discussed in this blog covers three crucial concepts:

1. Reversing a Linked List

2. Traversing a linked list and shuffling pointers

3. Some techniques to solve the Linked List problem like two pointer approach etc.

The problem statement is that we are given a linked list containing n nodes. Now we need to rearrange the linked in such a way that if the linked list initially looked like

Node_{1} , Node_{2} , …………….., Node_{n-1} Node_{n} ; now it should look like

Node_{1} , Node_{n} , Node_{2} , Node_{n-1} … .

So if you notice, we need to rearrange the linked list in such a way that after

Node_{i} the next node should be Node_{n-i+1} where i != n-i+1.

Let’s Understand the problem by taking an example:

You are given the following linked list with N = 6 nodes.

Now let us walk you through the example:

We have to rearrange the linked list such that after Node_{i} the next node should be Nord_{n-i+1} where i != n-i+1.

So we will put 6 after 1.

Now linked list will look like the following:

Now we will put 5 after 2,

Hence the linked list will look like the following:

Finally, we have to place 4 after 3, which is the case in the above illustration. Hence, we are done with rearranging the linked list.

I hope you got the essence of the question from the above example. If not, then no worries, we will discuss the approach here.

Recommended Topic, __Floyds Algorithm__ And __Rabin Karp Algorithm__

**Approach**

Let’s look at the approach that comes to our mind first.

So what we need to do is for a node at a K distance from the right to be placed after the node at a K distance from the left.

So the approach becomes simple.

- Find the node at the end of the linked list.
- Put it after the current node and move on to the next node, after which we have to put the node at the end.
- Repeat the same process above until the node to be placed after the current node is not the node itself.

(The connection of the list is maintained after rearranging the nodes so that we don’t lose the nodes).

Don’t worry about the time complexity here; we will have a look at it later on.

Now we can think of a PseudoCode.