Q.Read a list of n elements. Pass this list to a function which reverses this list in-place without creating a new list.

In-Place List Reversal: The Intuition

Imagine you have a line of numbered cards on a table, face up, in order: 1, 2, 3, 4, 5. You want to reverse the order so they read 5, 4, 3, 2, 1. The simplest way is to pick up all five cards, flip the stack over, and put them back down. That's a new arrangement, but you used extra space — the space in your hand to hold the whole stack.

Now imagine you're not allowed to pick up more than two cards at a time. You can only swap two cards at a time, directly on the table. How would you reverse the line?

You'd swap the first and last cards: 1 and 5 become 5 and 1. Then swap the second and second-last: 2 and 4 become 4 and 2. The middle card (3) stays where it is. After three swaps, the line is reversed. You never needed a second table or a pile in your hand — you did it in place, using only a constant amount of extra space (just enough to hold one card temporarily during a swap).

That's the core idea: in-place reversal means reversing the order of elements in a list without creating a separate copy of the list. You rearrange the existing elements by swapping pairs from the outside in.

The Precise Statement

Given a list (or array) $A$ of $n$ elements indexed from $0$ to $n-1$, an in-place reversal transforms $A$ so that after the operation:

and the operation uses only $O(1)$ extra memory (a constant number of temporary variables), regardless of $n$.

The algorithm is:

1. Set two pointers: left = 0, right = n-1.
2. While left < right:
   • Swap A[left] and A[right].
   • Increment left by 1, decrement right by 1.

Why It Works

Each swap places the element that belongs at position left (which originally was at position right) into its correct reversed position, and vice versa. The pointers move inward, so every element gets moved exactly once. When left meets or passes right, all pairs have been swapped and the list is fully reversed.

For an even-length list, every element is paired and swapped. For an odd-length list, the middle element stays in place — it's already in its correct reversed position.

Complexity …