/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

ListNode* reverse(ListNode* A){
    ListNode *prev = NULL, *current = A, *next = NULL;

    while(current){
        next = current -> next;
        current -> next = prev;

        prev = current;
        current = next;
    }

    return prev;
}

ListNode* Solution::reorderList(ListNode* A) {
    if(A==NULL) return NULL;

    ListNode *dum = A;
    int length = 0;
    while(dum){
        length++;
        dum = dum -> next;
    }
    // cout<<"length: "<<length<<endl;

    dum = A;
    ListNode *rev = reverse(dum);
    ListNode *finalHead = NULL;
    ListNode *finalTail = NULL;

    for(int i=0; i<length; ++i){
        ListNode *added;
        if(i%2==0){
            added = dum;
            if(dum)
                dum = dum -> next;
        }
        else{
            added = rev;
            if(rev)
                rev = rev -> next;
        }

        if(added){
            added -> next = NULL;
        }

        if(finalHead==NULL){
            finalHead = added;
            finalTail = added;
        }
        else{
            finalTail -> next = added;
            finalTail = added;
        }
    }

    return finalHead;
}