Reverse the Chain
EasyLinked ListFree
Problem
You are given the head of a singly linked list. Reverse the list in place and return the new head.
Each node has a val and a next pointer. Do not create new nodes.
Example 1
- Input:
- head = [1, 2, 3, 4]
- Output:
- [4, 3, 2, 1]
Example 2
- Input:
- head = [7]
- Output:
- [7]
Example 3
- Input:
- head = []
- Output:
- []
Constraints
- 0 ≤ number of nodes ≤ 5000
- -5000 ≤ node.val ≤ 5000
Hint
Show the first hint
Each node only needs its next pointer flipped to point at the node before it.
Walkthrough
How to approach it
01Clarify before coding
- Can the list be empty? Yes: return null / None.
- Must it be in place? Yes, reuse the existing nodes; O(1) extra space is expected.
- Is recursion acceptable? It works, but 5000 nodes deep is risky in Python's default recursion limit; iterate.
02Brute force
Copy the values into an array, then write them back in reverse order (or build a new list).
Cost: O(n) time and O(n) extra space; it also changes values instead of links, which interviewers usually reject.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.