To reverse the linked list in place, iterate through the nodes, updating each node's next pointer. The iterative method uses constant space, while recursion adds a stack-based space complexity.
Problem Statement
Given the head of a singly linked list, reverse the list in place, updating the next pointers of each node so that the original tail becomes the new head. You must return the new head after the reversal.
The reversal should be done in place, meaning no extra space is used for a new list. After reversal, the original head becomes the tail of the list. Consider the edge case where the list is empty or consists of a single node.
Examples
Example 1
Input: head = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]
Each node's next pointer is flipped so the original tail becomes the new head.
Example 2
Input: head = []
Output: []
An empty list stays empty. This is a useful edge case to call out before coding.
Constraints
- 0 <= number of nodes <= 5000
- -5000 <= Node.val <= 5000
- The list is singly linked, so each node only points forward in the original input.
- Returning the new head is required because the original head becomes the tail.
Solution Approach
Iterative Approach
In the iterative approach, use three pointers: previous, current, and next. Start with previous as null, current as the head, and next as null. Traverse the list, at each step, reverse the direction of the current node’s pointer. This approach has O(n) time complexity and uses O(1) space because it only updates pointers without needing extra data structures.
Recursive Approach
The recursive approach also reverses the list by reaching the end first and then reversing the pointer direction as the recursion unwinds. The base case is when the current node is null or the next node is null. This method has O(n) time complexity but uses O(n) space due to the function call stack.
Edge Cases
Consider the edge case of an empty list or a single-node list. These should return the list as-is. It's essential to handle these cases without additional computation to avoid unnecessary operations.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(1) for the iterative solution |
The iterative solution runs in O(n) time because each node is visited once. It uses O(1) space since it only requires a few pointer variables. The recursive approach also runs in O(n) time but uses O(n) space because of recursion stack frames for each node.
What Interviewers Usually Probe
- Do you know how to handle pointer updates safely without losing references to nodes?
- Can you explain the difference in space complexity between the iterative and recursive solutions?
- Are you familiar with edge cases such as empty lists or lists with only one element?
Common Pitfalls or Variants
Common pitfalls
- Failing to maintain the correct order of nodes during pointer reversal, leading to lost references.
- Overcomplicating the solution with extra data structures, which isn't needed for in-place reversal.
- Forgetting to handle the case where the list is empty or has only one node.
Follow-up variants
- Reverse a doubly linked list in place.
- Reverse a linked list in groups of k nodes.
- Reverse a linked list in a more memory-efficient way using tail recursion.
How GhostInterview Helps
- Take a screenshot of your work to visually identify pointer updates and tracking.
- Follow the answer path, including iterative vs. recursive solutions, to see space-time trade-offs.
- Explore supported screen-share workflows to demonstrate the process and answer specific questions.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
How can I reverse a linked list iteratively?
You can reverse the list iteratively by using three pointers: previous, current, and next. Traverse the list, updating each node's next pointer.
What is the time complexity of reversing a linked list?
Reversing the list takes O(n) time, where n is the number of nodes, because each node is visited once.
Why is the recursive solution slower than the iterative one?
The recursive solution has the same time complexity as the iterative one, but it uses additional memory due to the function call stack.
How do I handle an empty list in this problem?
If the list is empty, simply return the head as null without performing any reversal, as there's nothing to reverse.
What is the iterative method's advantage over the recursive one?
The iterative method uses constant space (O(1)), making it more memory-efficient compared to the recursive method, which uses O(n) space.
Need direct help with Reverse Linked List instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Reverse Linked List from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Two Sum is solved fastest by storing seen values in a hash map and checking each number's needed complement once.
Open problem page#207 Course ScheduleDetermine if all courses can be completed by analyzing prerequisite dependencies using indegree tracking and topological sorting to detect cycles.
Open problem page