// O(n) space, O(n) time
void reorderList(ListNode *head) {
if (!head) return;
vector<ListNode *> vl;
while (head) {
vl.push_back(head);
head = head>next;
}
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;
}
A concise solution using O(N) extra space, is it satisfy the in place algorithm condition ?


finally i implemented an O(n) time, O(1) in place solution, here is the link:
https://oj.leetcode.com/discuss/21992/aconciseontimeo1inplacesolution