Watch 10 video solutions for Reverse Linked List II, a medium level problem involving Linked List. This walkthrough by NeetCode has 539,243 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |