// O(N) time, O(1) space in total
void reorderList(ListNode *head) {
if (!head  !head>next) return;
// find the middle node: O(n)
ListNode *p1 = head, *p2 = head>next;
while (p2 && p2>next) {
p1 = p1>next;
p2 = p2>next>next;
}
// cut from the middle and reverse the second half: O(n)
ListNode *head2 = p1>next;
p1>next = NULL;
p2 = head2>next;
head2>next = NULL;
while (p2) {
p1 = p2>next;
p2>next = head2;
head2 = p2;
p2 = p1;
}
// merge two lists: O(n)
for (p1 = head, p2 = head2; p1; ) {
auto t = p1>next;
p1 = p1>next = p2;
p2 = t;
}
//for (p1 = head, p2 = head2; p2; ) {
// auto t = p1>next;
// p1>next = p2;
// p2 = p2>next;
// p1 = p1>next>next = t;
//}
}
A concise O(n) time, O(1) in place solution


2 improvements needed to pass all test cases

If list contains only 2 nodes, check the condition at the top and return. There is no need to process further.
if(!head  !head>next  !head>next>next) return; 
For lists that contain even no of nodes. For example 1>4>3>2. Your solution returns 1>4>3. For the solution to work for this case I made the following change.
ListNode *prev=NULL;
for (p1 = head, p2 = head2; p1; ) {
auto t = p1>next;
prev=p1;
p1 = p1>next = p2;
p2 = t;
}
if(p2)
{
prev>next=p2;
}

