# 143 - Reorder List (同時從前後往中間移動)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head || !head->next) return;

        vector<ListNode *> vl;
        while (head) { 
            vl.push_back(head); 
            head = head->next;
        }

        // reassign the next pointer
        int n = vl.size();
        int i = 0, j = n - 1;
        while ( i < j) {
            if (j == i+1) break;
            vl[i]->next = vl[j];
            vl[j]->next = vl[i+1];
            ++i, --j;
        }

        vl[j]->next = NULL;
    }
};