/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  void rearrangedList(ListNode* head) {
    vector<ListNode*> v;
    for (auto p = head; p; p = p->next)
      v.emplace_back(p);

    for (int i = 0; i < v.size() / 2; ++i) {
      v[i]->next = v[v.size() - 1 - i];
      v[v.size() - 1 - i]->next = v[i + 1];
    }
    v[v.size() / 2]->next = nullptr;
  }
};