Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5], left = 2, right = 4 Output: [1,4,3,2,5]
Example 2:
Input: head = [5], left = 1, right = 1 Output: [5]
Constraints:
n.1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= nFollow up: Could you do it in one pass?
Problem Overview: Reverse a portion of a singly linked list from position left to right (1-indexed) while keeping the rest of the list unchanged. The challenge is reconnecting the reversed sublist correctly without breaking the list structure.
Approach 1: Iterative In-Place Reversal (O(n) time, O(1) space)
You iterate through the linked list until reaching the node right before the left position. From there, perform a standard linked list reversal for the next right - left + 1 nodes using pointer manipulation. The key trick is maintaining three references: the node before the sublist, the start of the sublist, and the node that moves during reversal. After reversing, reconnect the tail of the reversed segment to the remaining list. This approach avoids extra memory and performs all operations directly on node pointers.
Most implementations use a dummy node before the head to simplify edge cases such as reversing from position 1. During reversal, repeatedly move the next node in the segment to the front of the sublist. Each pointer adjustment is constant time, so the full traversal remains linear.
Approach 2: Recursive In-Place Reversal (O(n) time, O(n) space)
The recursive solution breaks the task into two parts: moving the head pointer until it reaches the left position, then reversing the first right - left + 1 nodes using recursion. A helper function reverses the first n nodes of a list and keeps track of the successor node (the node immediately after the reversed segment). After the recursive reversal completes, the original head reconnects to that successor.
This technique relies on the call stack instead of explicit loops. The logic is elegant and closely mirrors the conceptual definition of reversing nodes. However, recursion introduces O(n) auxiliary stack space, which makes it less memory-efficient than the iterative approach. The method still performs only one traversal of the list.
Recursive pointer manipulation is a common pattern when working with recursion on linked structures. It helps build intuition for problems that reverse segments or swap nodes in place.
Recommended for interviews: The iterative in-place reversal is the expected solution. It runs in O(n) time and O(1) space while handling edge cases cleanly with a dummy node. Interviewers want to see correct pointer manipulation and careful reconnection of the reversed segment. The recursive version shows deeper understanding of linked list recursion but is usually presented as an alternative rather than the primary solution.
This approach involves reversing the sublist in place by iterating from the left to the right node. We will use a dummy node to ensure that edge cases where the reversal starts at the head of the list are handled smoothly. During the iteration, we carefully manipulate the pointers to reverse the section of the list between the given positions.
The code initializes a ListNode class to represent each node. The reverseBetween method begins by creating a dummy node that precedes the head of the list, which allows us to manage edge cases where the head itself needs modification.
We identify the node before the left position, referred to as prev, and initiate a standard pointer reversal technique for the sublist. This involves switching the next pointers within the range of left and right to achieve the desired reversal.
Java
C++
C
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes in the list. We do a single pass over the list between left and right.
Space Complexity: O(1), since no additional data structures are used.
In this approach, we leverage recursion to reverse the sublist between the given positions. The primary idea is to handle the reversal within the recursive call stack, ensuring the in-place modification of the linked list while managing the sublist reversal inherently through recursive stack control.
Here, we define a recursive inner function reverse which handles the reversal of the initial segment of the list up to the right-left position. The recursion unfolds with the base case for n = 1. The main function drive adjusts to skip the initial non-reversal nodes as needed before invoking the recursive calls.
Time Complexity: O(n), where n is the total number of nodes in the list.
Space Complexity: O(n), due to recursive call stack depth based on n.
| Approach | Complexity |
|---|---|
| Iterative In-Place Reversal | Time Complexity: O(n), where n is the number of nodes in the list. We do a single pass over the list between left and right. |
| Recursive In-Place Reversal | Time Complexity: O(n), where n is the total number of nodes in the list. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative In-Place Reversal | O(n) | O(1) | Best general solution for interviews and production. Minimal memory and straightforward pointer updates. |
| Recursive In-Place Reversal | O(n) | O(n) | Useful for learning recursive linked list manipulation or when recursion-based patterns are preferred. |
Reverse Linked List - Iterative AND Recursive - Leetcode 206 - Python • NeetCode • 539,243 views views
Watch 9 more video solutions →Practice Reverse Linked List II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor