LeetCode問題解:Reorder List

Reorder List
Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes' values.
For example, Given {1,2,3,4} , reorder it to {1,4,2,3} .
考え方:
チェーンテーブルは一方向であり,ループによってしか尾が見つからないため,ここではチェーンテーブルの各ノードをポインタ配列で保存する方式を採用した.
問題:

/**
 * 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 == nullptr)
            return;
        
        vector<ListNode*> nodes;
        ListNode* iter = head;
        while(iter != nullptr)
        {
            nodes.push_back(iter);
            iter = iter->next;
        }
        
        int LEN = nodes.size();
        int left = 0;
        int right = LEN -1;
        while(left < right)
        {
            nodes[left]->next = nodes[right];
            nodes[right--]->next = nodes[++left];
        }
        nodes[left]->next = nullptr;
    }
};