Suppose we have an array a1, a2,... , an, b1, b2, ..., bn.
The goal is to change this array to a1, b1, a2, b2, ..., an, bn in O(n) time and in O(1) space. In other words, we need a linear-time algorithm to modify the array in place, with no more than a constant amount of extra storage.
How can this be done?