# Three step solution (C++ O(N) time, O(1) space)

#1
``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/

// Add val to tail of list
void push(ListNode **head, ListNode **tail, ListNode *val)
{
else {
(*tail)->next = val;
*tail = (*tail)->next;
}
}

// Split as per even and odd positions
pair<ListNode *, ListNode *>
{
ListNode *oddH = nullptr, *oddT = nullptr;
ListNode *eveH = nullptr, *eveT = nullptr;
int pos = 1;
// Isolate node
if (pos & 1) // Odd
else
++pos;
}

return {oddH, eveH};
}

// Reverse list
ListNode *
{
ListNode *prev = nullptr;
}

return prev;
}

// Given list A and B, return a list with elements from A and B in interleaving manner
ListNode *
mergeLists(ListNode *A, ListNode *B)
{
ListNode *head = nullptr, *tail = nullptr;
while (A and B) {
ListNode *nextA = A->next, *nextB = B->next;
A->next = nullptr, B->next = nullptr;
A = nextA, B = nextB;
}
if (A) tail->next = A;
if (B) tail->next = B;

}

ListNode* Solution::solve(ListNode* A) {

// Step 1 : Divide into two lists as per odd and even positions
ListNode *odd, *even;
tie(odd, even) = split(A);

// Step 2 : Reverse the even list
even = reverse(even);

// Step 3 : Merge the odd list and reversed even list interleavingly
ListNode *merged = mergeLists(odd, even);

return merged;
}``````