class Solution {
public:
    void reorderList(ListNode *head) {
        if (head == NULL || head->next == NULL || head->next->next == NULL)
            return;
        ListNode** left = &head;
        ListNode** right = left;
        while (*left != NULL && (*left)->next != NULL) {
            while (*right != NULL && (*right)->next != NULL) {
                right = &(*right)->next;
            }
            ListNode* tail = *right;
            *right = NULL;
            tail->next = (*left)->next;
            (*left)->next = tail;
            left = &(*left)->next->next;
            right = left;
        }
        return;
    }
};