/*
 * Complete the function below.
 */
/*
For your reference:
LinkedListNode {
    int val;
    LinkedListNode *next;
};
*/
LinkedListNode* reverseList(LinkedListNode* head)
{
    LinkedListNode* prev = NULL;
    LinkedListNode* succ = NULL;

    LinkedListNode* curr = head;

    while(curr != NULL)
    {
        succ = curr->next;
        curr->next = prev;
        prev  = curr;
        curr = succ;
    }
    return prev; //prev will contain the head of reversed List
}

LinkedListNode* mergeLists(LinkedListNode* l1, LinkedListNode* l2)
{
    LinkedListNode* sentinel = (LinkedListNode*)malloc(sizeof(LinkedListNode));

    sentinel->next = NULL;

    LinkedListNode* curr = sentinel;

    while(l1 != NULL && l2 != NULL)
    {
        curr->next = l1;
        curr = l1;
        l1 = l1->next;

        curr->next = l2;
        curr =l2;
        l2 = l2->next;

    }

    // if Odd list, then l1 wouldn't be null and we need to add extra element at end
    if(l1 != NULL)
    {
        curr->next = l1;
    }

    return sentinel->next;

}

LinkedListNode* zip_given_linked_list(LinkedListNode* head) {


    if(head == NULL)
    {
        return NULL;
    }


    // Find the middle of List and split into 2 lists
    // reverse the 2nd list
    // Merge both the list
    // if Odd list, then add extra element at end

    //T(n) = O(n)
    // Aux space = O(1)

    LinkedListNode* slow = head;
    LinkedListNode* fast = head;

    LinkedListNode* head1 = NULL;

    while(fast->next != NULL && fast->next->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    // Slow pointer at middle
    head1 = slow->next;
    slow->next = NULL;

    // Reverse second List
    head1 = reverseList(head1);

    // Merge the two lists
    head = mergeLists(head, head1);

    return head;

}