Reverse a Singly Linked List
Company: Bytedance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Reverse a Singly Linked List
You are given the `head` of a singly linked list. Each node stores an integer value and a pointer to the next node. Reverse the order of the nodes in the list and return the head of the reversed list.
For example, the list
```
1 -> 2 -> 3 -> 4 -> 5 -> null
```
should become
```
5 -> 4 -> 3 -> 2 -> 1 -> null
```
After reversal, the node that was originally last becomes the new head, and the node that was originally first points to `null`.
### Node definition
Each node has the shape:
```
Node {
int val
Node next // null for the last node
}
```
### Input / Output
- **Input:** the `head` node of the list (may be `null` for an empty list).
- **Output:** the `head` node of the fully reversed list.
You should return the new head; do not allocate a brand-new list if you can rewire the existing nodes in place.
### Examples
| Input list | Output list |
|---|---|
| `1 -> 2 -> 3 -> 4 -> 5` | `5 -> 4 -> 3 -> 2 -> 1` |
| `1 -> 2` | `2 -> 1` |
| `7` | `7` |
| `` (empty) | `` (empty) |
### Constraints
- The number of nodes `n` satisfies `0 <= n <= 5 * 10^4`.
- Each node value fits in a 32-bit signed integer.
- Aim for `O(n)` time. An in-place solution uses `O(1)` extra space; a recursive solution is also acceptable but uses `O(n)` stack space — be ready to discuss the trade-off.
### Follow-up
Can you implement the reversal both iteratively and recursively, and explain the difference in space usage?
Quick Answer: This question evaluates a candidate's grasp of linked list pointer manipulation and in-place data structure transformation. It tests the ability to rewire node references without extra memory, a core data structures and algorithms skill frequently assessed in coding interviews at both conceptual and hands-on implementation levels.
You are given the `head` of a singly linked list, represented here as an array of node values in head-to-tail order (`[1, 2, 3, 4, 5]` means `1 -> 2 -> 3 -> 4 -> 5 -> null`). Reverse the order of the nodes and return the reversed list, again as an array of values.
Example:
```
Input: [1, 2, 3, 4, 5] (1 -> 2 -> 3 -> 4 -> 5 -> null)
Output: [5, 4, 3, 2, 1] (5 -> 4 -> 3 -> 2 -> 1 -> null)
```
After reversal the node that was originally last becomes the new head, and the node that was originally first points to `null`. An empty list (`[]`) reverses to an empty list.
Aim for `O(n)` time. The in-place iterative approach rewires the existing `next` pointers and uses only `O(1)` extra space; a recursive approach is also acceptable but uses `O(n)` stack space.
**Follow-up:** Can you implement the reversal both iteratively and recursively, and explain the difference in space usage?
Constraints
- 0 <= n <= 5 * 10^4 (number of nodes)
- Each node value fits in a 32-bit signed integer
- The empty list reverses to the empty list
Examples
Input: ([1, 2, 3, 4, 5],)
Expected Output: [5, 4, 3, 2, 1]
Explanation: The five-node list is fully reversed; the old tail (5) is the new head.
Input: ([1, 2],)
Expected Output: [2, 1]
Explanation: A two-node list swaps head and tail.
Input: ([7],)
Expected Output: [7]
Explanation: A single node reverses to itself.
Input: ([],)
Expected Output: []
Explanation: Empty list edge case: reversing an empty list yields an empty list.
Input: ([-1, -2, -3],)
Expected Output: [-3, -2, -1]
Explanation: Negative values are handled the same as positives; only the order changes.
Input: ([5, 5, 3, 3, 3],)
Expected Output: [3, 3, 3, 5, 5]
Explanation: Duplicate values are preserved; reversal only reorders the nodes.
Hints
- Walk the list once, keeping three pointers: `prev` (already-reversed portion), `cur` (node being processed), and `nxt` (saved so you don't lose the rest of the list).
- For each node, save `nxt = cur.next`, point `cur.next` back to `prev`, then advance `prev = cur` and `cur = nxt`.
- When `cur` becomes null, `prev` is the new head. This handles the empty and single-node cases without any special casing.
- Recursive alternative: reverse `head.next`, then set `head.next.next = head` and `head.next = None`. It's O(n) time but O(n) stack space.