Reverse Linked List II - Solution & Explanation

Problem Overview: Reverse a section of a singly linked list between positions left and right (1-indexed) while keeping the rest of the list unchanged. The challenge is updating pointers correctly so the reversed sublist reconnects with the original list.

Approach 1: Iterative In-Place Reversal (O(n) time, O(1) space)

This approach walks the list once and reverses only the portion between left and right. First, iterate to the node just before the reversal region using a pointer like prev. From there, perform an in-place reversal using the classic linked list reversal technique: repeatedly move the next node in the segment to the front of the sublist. The key insight is that you do not reverse the entire list; you only manipulate pointers within the specified window while keeping track of the connection points before and after the segment.

A dummy node simplifies edge cases where the reversal starts at the head. During each iteration, you detach the next node and insert it at the beginning of the reversed portion. This effectively builds the reversed sublist while preserving constant extra memory. Since every node is visited at most once, the time complexity is O(n) and the space complexity remains O(1). This method is the most common implementation expected in interviews involving linked list pointer manipulation.

Approach 2: Recursive In-Place Reversal (O(n) time, O(n) space)

The recursive strategy breaks the problem into two smaller tasks: moving the head of the list until it reaches the left boundary, then reversing the next right - left + 1 nodes recursively. A helper function performs the reversal of the first k nodes and returns the new head of that reversed segment. During recursion unwinding, pointers reconnect the reversed segment with the remaining list.

This technique relies on the call stack to keep track of previous nodes, which introduces O(n) auxiliary space due to recursion depth. The advantage is conceptual clarity—once you define a function that reverses the first k nodes, the rest of the logic becomes straightforward. Problems that involve partial reversal often combine recursion with pointer tracking, making this a useful pattern when practicing recursion on linked structures.

Recommended for interviews: The iterative in-place reversal is what most interviewers expect. It runs in O(n) time with O(1) space and demonstrates strong pointer control in linked lists. The recursive solution shows conceptual understanding but uses additional stack space. Explaining both approaches—starting with the straightforward recursive idea and then optimizing to the iterative constant-space version—demonstrates strong problem-solving depth.