# Rearrange a given linked list in-place

## Given a singly linked list L0-> L1-> … -> Ln-1-> Ln. Rearrange the nodes in the list so that the new formed list is : L0-> Ln-> L1-> Ln-1-> L2-> Ln-2…

### Example

INPUT :
1->2 ->3 ->4 ->5

OUTPUT :
1 ->5 ->2 ->4 ->3

Time Complexity : O(n)

## Algorithm

1. Find the middle point using tortoise and hare method
a. Take two variables slow, fast. Move fast two steps ahead and move slow only one step ahead for every iteration.

b. By the end of the list, slow will point to the middle point of the linkedlist

2. Split the linked list into two halves using the middle point

3. Reverse the second half

4. Do alternate merge of first and second halves

Implementation of Algorithm for above example

1. Middle point is the node 3

2. list1 = 1->2->3, list2 = 4->5

3. Reverse the second list.
list1 = 1->2->3, list2 = 5->4

4. Alternate Merge
result = 1 ->5 ->2 ->4 ->3

## C++ Program

```#include <bits/stdc++.h>
using namespace std;

struct LLNode{
int data;
LLNode *next;
};
// Function to create newNode in a linkedlist
LLNode* newNode(int data)
{
LLNode *temp = new LLNode;
temp->data = data;
temp->next = NULL;
return temp;
}
// Function to reverse the linked list
{
// Initialize prev and current pointers
LLNode *prev = NULL, *curr = *head, *next;

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

}
// Function to rearrange a linked list
{
// 1) Find the middle point using tortoise and hare method
LLNode *slow = *head, *fast = slow->next;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}

// 2) Split the linked list in two halves
LLNode *list2 = slow->next;
slow->next = NULL;

// 3) Reverse the second half
reverselist(&list2);

// 4) Merge alternate nodes
*head = newNode(0); // Assign dummy Node

// curr is the pointer to this dummy Node, which will
// be used to form the new list
while (list1 || list2)
{
// First add the element from first list
if (list1)
{
result->next = list1;
result = result->next;
list1 = list1->next;
}

// Then add the element from second list
if (list2)
{
result->next = list2;
result = result->next;
list2 = list2->next;
}
}
}
{
LLNode*curr=new LLNode;
//make a new node with this data and next pointing to NULL
curr->data=dataToBeInserted;
curr->next=NULL;

if(*head==NULL) //if list is empty then set the current formed node as head of list

else //make the next of the current node point to the present head and make the current node as the new head
{
}

//O(1) constant time
}

{
while(temp!=NULL) //till the list ends (NULL marks ending of list)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

int main()
{

LLNode *head = NULL; //initial list has no elements