Node<int>* rearrange(Node<int> *head){
	// Write your code here
    if(head == NULL){
        return NULL;
    }
    else if(head->next == NULL){
        return head;
    }
    Node<int> *fast = head;
    Node<int> *slow = head;
    while(fast == NULL && fast->next == NULL){
        fast = fast->next->next;
        slow = slow->next;
    }
    Node<int> *head2 = slow->next;
    slow->next = NULL;
     Node<int> *head1 = head;
    //reverse 2nd ll
    Node<int> *curr = head2;
    Node<int> *n;
    Node<int> *prev = NULL;
    while(curr!=NULL){
        n = curr->next;
        curr->next = prev;
     	prev = curr;
        curr = n;
    }
    head2 = prev;
    //merge
    Node<int> *temp_head = NULL;
    Node<int> *temp = temp_head;
    while(head1 || head2){
        if(head1){
            temp->next = head1;
            temp = temp->next;
            head1 = head1->next;
        }
        if(head2){
            temp->next = head2;
            temp = temp->next;
            head2 = head2->next;
        }
    }
   	temp_head->next = temp;
    return temp;
}