If you are preparing for software engineering interviews, you already know that Linked Lists are a favourite topic among interviewers. While reversing an entire linked list is a standard beginner problem, reversing only a specific section of it requires a bit more pointer magic.

In this blog post, we will tackle LeetCode 92. Reverse Linked List II. We will break down the problem in plain English, walk through a highly intuitive modular approach, and then look at an optimized one-pass technique.

Let’s dive in!

Understanding the Problem

Question Statement:

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
2. Output: [1,4,3,2,5]

In Simple Words:

Imagine a chain of connected boxes. You don't want to flip the whole chain backwards. You only want to flip a specific middle section (from the 2nd box to the 4th box), while keeping the first and last boxes exactly where they are.

Approach 1: The Intuitive Modular Approach (Find, Reverse, Connect)

When solving complex linked list problems, breaking the problem into smaller helper functions is an excellent software engineering practice.

In this approach, we will:

1. Use a Dummy Node. This is a lifesaver when left = 1 (meaning we have to reverse from the very first node).
2. Traverse the list to find the exact boundaries: the node just before the reversal (slow), the start of the reversal (leftNode), and the end of the reversal (rightNode).
3. Pass the sub-list to a helper function that reverses it.
4. Reconnect the newly reversed sub-list back to the main list.

Here is the Java code for this approach:

🔍 Dry Run of Approach 1

Let’s trace head = [1, 2, 3, 4, 5], left = 2, right = 4.

Step 1: Initialization

1. dummy = -1 -> 1 -> 2 -> 3 -> 4 -> 5
2. slow = -1 (dummy node)

Step 2: Finding Bounds (While Loop)

1. We move curr through the list.
2. When curr is at 1 (Position 1): left - 1 is 1, so slow becomes node 1.
3. When curr is at 2 (Position 2): leftNode becomes node 2.
4. When curr is at 4 (Position 4): rightNode becomes node 4. We break the loop.

Step 3: The Helper Reversal

1. We call reverse(leftNode, rightNode.next), which means reverse(Node 2, Node 5).
2. Inside the helper, we reverse the links for 2, 3, and 4.
3. Because we initialized prev as rightHead (Node 5), Node 2's next becomes Node 5.
4. The helper returns Node 4 as the new head of this reversed chunk. The chunk now looks like: 4 -> 3 -> 2 -> 5.

Step 4: Reconnection

1. Back in the main function, slow (Node 1) is connected to the returned reversed list: slow.next = rev.
2. Final List: dummy -> 1 -> 4 -> 3 -> 2 -> 5.
3. Return dummy.next!

Time & Space Complexity:

1. Time Complexity: O(N). We traverse the list to find the pointers, and then the helper traverses the sub-list to reverse it. Since we visit nodes a maximum of two times, it is linear time.
2. Space Complexity: O(1). We are only creating a few pointers (dummy, slow, curr, etc.), requiring no extra dynamic memory.

Approach 2: The Optimized One-Pass Solution

LeetCode includes a follow-up challenge: "Could you do it in one pass?"

While the first approach is incredibly readable, we can optimize it to reverse the nodes as we traverse them, eliminating the need for a separate helper function or a second sub-list traversal.

In this approach, we:

1. Move a prev pointer to the node just before left.
2. Keep a curr pointer at left.
3. Use a for loop to extract the node immediately after curr and move it to the front of the reversed sub-list. We do this exactly right - left times.

🔍 Why this works (The Pointer Magic)

If we are reversing [1, 2, 3, 4, 5] from 2 to 4:

1. prev is at 1. curr is at 2.
2. Iteration 1: Grab 3, put it after 1. List: [1, 3, 2, 4, 5].
3. Iteration 2: Grab 4, put it after 1. List: [1, 4, 3, 2, 5].
4. Done! We achieved the reversal in a strict single pass.

Time & Space Complexity:

1. Time Complexity: O(N). We touch each node exactly once.
2. Space Complexity: O(1). Done entirely in-place.

Conclusion

Reversing a portion of a linked list is a fantastic way to test your understanding of pointer manipulation.

1. Approach 1 is amazing for interviews because it shows you can modularize code and break big problems into smaller, testable functions.
2. Approach 2 is the perfect "flex" to show the interviewer that you understand optimization and single-pass algorithms.

I highly recommend writing down the dry run on a piece of paper and drawing arrows to see how the pointers shift. That is the secret to mastering Linked Lists!

Happy Coding! 💻🚀