# Rearrange a given Linked List in-place ### Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

### Problem Statement

In this question, we are given a singly linked list. We have to rearrange it in place, in which there are alternating first and last nodes. Let us have a look at the input and output to get a clearer understanding of the problem.

### Problem Statement Understanding

Let’s try to understand the problem statement with help of examples. As we can see, It is of the form: Now, we have to rearrange the list, so that it becomes of the form: i.e. Alternating first and last elements. will transform to  So, the final linked list after rearrangement will be: If the given linked list is: Then, after rearrangement, the linked list will transform to: Now, I think it is clear from the examples what we have to do in this problem. This is an interesting question. We have to make use of list traversal to obtain the desired output. The traversal is not going to be a simple one. We are going to tweak it a bit.

Try to think how we can approach this problem, if you are not able to get an optimized approach no problem think of brute force, and then we will try to optimize it together.

Now, we will see brute force approach, as well as an efficient approach.

### Approach and Algorithm (Brute Force)

This approach is going to be pretty simple. We are going to create a node current and point it to the head. Then, while the current node is not NULL, we will find the last node, delete it from the end, and insert it just after the current node. After this step, we will increment the current node by 2 places, as we have now successfully inserted the last node after the first node. This process will continue till we reach the end of the list.

Time Complexity - O(n2), as we have to do a nested traversal of the given list
Space Complexity - O(1), as only temporary variables are being created.

### Approach and Algorithm (Vector rearranging method)

In this approach, we will copy all the elements of the list to a vector. Now, we will traverse through the vector up to its middle (l/2, where l is the length of the vector), and insert the ith node and the (n-i-1)th node in the list (where this i starts from 0). By doing this, we are creating the alternating list that we require.

Time Complexity - O(N), as a single list traversal is required.
Space Complexity - O(N), the space required to create a vector of size N.

### Approach and Algorithm (Linked List Splitting)

This is the most efficient solution. We are first going to divide the list into two halves. After the division, we will reverse the second half and then do an alternate merge of the first and second halves.

Let us have a glance at the algorithm.

### Algorithm

• Find the middle of the list using the slow and fast pointer technique. We are using the slow and fast pointer technique because it is the most efficient technique to find the middle of a linked list. Both pointers will point to the head of the list initially. Now, the fast pointer makes two jumps, and the slow pointer will make one jump. When the fast pointer will reach the end, the slow pointer will be at the middle of the list.
• After finding the middle, split the list into two halves. Create two nodes, say, head1 and head2, head1 will point to head, and head2 will point to slow → next. Now, make slow → next will point to NULL. By doing this, the division of the list is successful.
• Reverse the second half of the linked list using the list reversal technique.
• Now, alternatively add elements from the first list and second list as long as either of them exists.
• In the end, assign the head of the new list to the head pointer.

### Dry Run  ### Code Implementation

```#include <stdio.h>
#include <stdlib.h>

// Creating the structure for node
struct Node {
int data;
struct Node* next;
};

// Function to create newNode in a linkedlist
struct Node* newNode(int key)
{
struct Node* temp = malloc(sizeof(struct Node));
temp->data = key;
temp->next = NULL;
return temp;
}

// Function to print the list
{
printf("->");
}
printf("\n");
}

// Function to rearrange
void rearrange(struct Node** head, struct Node* last)
{

if (!last)
return;

// Recursive call

// (*head)->next will be set to NULL
// after rearrangement.
// Need not do any operation further
// Just return here to come out of recursion
return;

// Rearrange the list until both head
// and last meet or next to each other.
last->next = tmp;
}
else {
}
}

// Drivers Code
int main()
{

// Print original list

// Modify the list

// Print modified list
return 0;
}
```
```#include <bits stdc++.h>
using namespace std;

struct Node {
int data;
struct Node* next;
};

Node* newNode(int key)
{
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}

{

Node *prev = NULL, *curr = *head, *next;

while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}

}

{
cout << head->data << " ";
cout << "-> ";
}
cout << endl;
}

{

Node *slow = *head, *fast = slow->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}

slow->next = NULL;

curr = curr->next;
}

curr = curr->next;
}
}

}

int main()
{

return  0;
}
```
```class Node
{
int data;
Node next;
Node(int key)
{
data = key;
next = null;
}
}
class Inplace
{

Node left = null;

// Function to print the list
{
System.out.print("->");
}
}
System.out.println();
}
{

reorderListUtil(left);
}
}

void reorderListUtil(Node right)
{

if (right == null) {
return;
}

reorderListUtil(right.next);

// we set left = null, when we reach stop condition,
// so no processing required after that
if (left == null) {
return;
}

// Stop condition: odd case : left = right, even
// case : left.next = right
if (left != right && left.next != right) {
Node temp = left.next;
left.next = right;
right.next = temp;
left = temp;
}
else { // stop condition , set null to left nodes
if (left.next == right) {
left.next.next = null; // even case
left = null;
}
else {
left.next = null; // odd case
left = null;
}
}
}
public static void main(String[] args)
{

Inplace i=new Inplace();

// Print original list

// Modify the list

// Print modified list
}
}
```
```class Node:

def __init__(self, d):
self.data = d
self.next = None

def printlist(node):
if(node == None):
return
while(node != None):
print(node.data," -> ", end = "")
node = node.next

def reverselist(node):
prev = None
curr = node
next=None
while (curr != None):
next = curr.next
curr.next = prev
prev = curr
curr = next
node = prev
return node

def rearrange(node):

slow = node
fast = slow.next
while (fast != None and fast.next != None):
slow = slow.next
fast = fast.next.next

node1 = node
node2 = slow.next
slow.next = None
node2 = reverselist(node2)
node = Node(0)
curr = node

while (node1 != None or node2 != None):

if (node1 != None):
curr.next = node1
curr = curr.next
node1 = node1.next

if(node2 != None):
curr.next = node2
curr = curr.next
node2 = node2.next

node = node.next

print()

```

### Output

1 → 3 → 8 → 13
1 → 13 → 3 → 8

Time Complexity: O(n), as a list traversal is needed.

[forminator_quiz id="3893"]

So, in this article, we have tried to explain the most efficient approach to rearrange a given linked list in place. This is an important problem when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes visit Linked List.