Reverse a list in-place
Company: Microsoft
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
Implement a function that reverses a Python list in-place without allocating another list (no slicing, no list(), no reversed()). Requirements: O(n) time, O(1) extra space, and it must work for empty lists and odd/even lengths. Provide the function, brief correctness reasoning, and state the time/space complexity. Include tests that prove in-place behavior (e.g., the object id of the list is unchanged) and handle edge cases like [], [1], and [1, 4, 8, 12, 16, 20] → [20, 16, 12, 8, 4, 1].
Quick Answer: This question evaluates a candidate's ability to implement an in-place list reversal and the underlying competencies in array/list manipulation, index/pointer management, and analysis of space and time complexity.
Implement a function that reverses a list **in-place** without allocating a new list.
You must mutate the input list directly (no slicing such as `arr[::-1]`, no `list()`, no `reversed()`) and return it.
## Requirements
- **Time complexity:** O(n)
- **Extra space:** O(1) (only a constant number of index/temporary variables)
- Must work for empty lists, single-element lists, and both odd- and even-length lists.
## Example
```
Input: [1, 4, 8, 12, 16, 20]
Output: [20, 16, 12, 8, 4, 1]
```
## Approach
Use two pointers, `left` starting at index 0 and `right` at the last index. While `left < right`, swap the two elements and move the pointers toward the middle. Each element is touched at most once, and no auxiliary list is allocated.
Constraints
- 0 <= len(arr) <= 10^5
- Elements fit in a 32-bit signed integer
- Must reverse in-place: O(1) extra space
- No slicing, list(), or reversed() (Python); no built-in reverse helpers in other languages
Examples
Input: ([1, 4, 8, 12, 16, 20],)
Expected Output: [20, 16, 12, 8, 4, 1]
Explanation: Given even-length example reversed.
Input: ([],)
Expected Output: []
Explanation: Empty list stays empty; loop never runs.
Hints
- Use two pointers: one at the start, one at the end of the list.
- Swap the elements the two pointers reference, then move both pointers toward the middle.
- Stop when the left pointer meets or crosses the right pointer. For odd-length lists the middle element stays in place, which is correct.