# Rearrange a linked list such that all even and odd position nodes are together

## Given  a linked list, write a function such that all the even position nodes are together and all the odd position nodes are together

### Example

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

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

In this method we will modify the given input list

## Algorithm

1. Initialize "odd_list" and "even_list" pointers to the first odd node and first even node respectively

2. If there are no more elements left, then connect odd_list and even_list and break the loop.

3. Connect the odd nodes
odd_list->next = even_list->next;
odd_list = even_list->next;

4. If there are no even nodes left, then connect the odd list and even list and break the loop

5. Connect the even nodes
even_list->next = odd_list->next;
even_list = odd_list->next;

## C++ Program

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

struct LLNode{
int data;
LLNode *next;
};
//Rearranges list such that all odd positioned nodes
//are before even positioned nodes
{
// If no elments
return NULL;

// Initialize first nodes of even and
// odd lists

//to connect even list, we need to remember the even list start
LLNode *even_list_start = even_list;

while (1)
{
//If there are no nodes left, then connect even list to odd list
if (!odd_list || !even_list || !(even_list->next))
{
odd_list->next = even_list_start;
break;
}

// Connecting odd nodes
odd_list->next = even_list->next;
odd_list = even_list->next;

// If there are NO more even nodes after
// current odd.
if (odd_list->next == NULL)
{
even_list->next = NULL;
odd_list->next = even_list_start;
break;
}

// Connecting even nodes
even_list->next = odd_list->next;
even_list = odd_list->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
LLNode *result = NULL;