学步园

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-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;
    }
};