How do you reorder a linked list so that it becomes 1, n, 2, n minus 1 and so on?
You split the list in half, you reverse the second half, and then you weave the two halves together by taking one node from each in turn.
the list 1 -> 2 -> 3 -> 4 -> 5
the answer 1 -> 5 -> 2 -> 4 -> 3
So the three steps are these.
The first step is finding the middle. You use the fast and slow pointer trick, and the slow pointer stops on the last node of the first half.
The second step is reversing the second half. After that the second half points backwards, so you can take nodes from the front of it one at a time.
The third step is the weaving. You take one node from the first half, then one from the second half, then one from the first half again, and so on until both halves are used up.
the first half 1 -> 2 -> 3
the second half 4 -> 5
after the weave 1 -> 5 -> 2 -> 4 -> 3
And the complexity is O of n for the time, because you go through the list a constant number of times, and O of 1 for the space, because you make no new nodes. That last part is what makes it an "in place" solution, and it is the reason the question says in place.
And there is a detail worth knowing about the odd length case. If the list has an odd number of nodes then the first half is one node longer than the second half, and the weaving has to stop when the second half runs out. The usual way to handle it is to break out of the loop when the second pointer is nothing, and then the last node of the first half stays where it is.
And there is a second version of the question that is worth knowing about. It is the same shape but the answer starts from the other end, so a list of 1, 2, 3, 4, 5 becomes 5, 1, 4, 2, 3. You make the first half the longer one and then weave in the other order.
So the rule to remember is this. Split, reverse the second half, and then take one from each in turn.
The last question in this topic shows the code.