## 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
void reverselist(LLNode **head)
{
// Initialize prev and current pointers
LLNode *prev = NULL, *curr = *head, *next;
while (curr)
{
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
*head = prev;
}
// Function to rearrange a linked list
void rearrange(LLNode **head)
{
// 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 *list1 = *head;
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
LLNode *result = *head;
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;
}
}
// Assign the head of the new list to head pointer
*head = (*head)->next;
}
void insertAtBeginning(LLNode**head,int dataToBeInserted)
{
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
*head=curr;
else //make the next of the current node point to the present head and make the current node as the new head
{
curr->next=*head;
*head=curr;
}
//O(1) constant time
}
void display(LLNode**head)
{
LLNode*temp=*head;
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
insertAtBeginning(&head,5);
insertAtBeginning(&head,4);
insertAtBeginning(&head,3);
insertAtBeginning(&head,2);
insertAtBeginning(&head,1);
cout<<"\nCurrent List is :-\n";
display(&head);
rearrange(&head);
cout<<"After rearranging the elements"<<endl;
display(&head);
return 0;
}
```