Problem Description

You are given the head of a singly linked list and two integers left and right where left <= right. Your task is to reverse the nodes of the linked list from position left to position right (positions are 1-indexed), and return the modified list.

For example, if you have a linked list 1 -> 2 -> 3 -> 4 -> 5 and left = 2, right = 4, you need to reverse the portion from position 2 to position 4. The result would be 1 -> 4 -> 3 -> 2 -> 5.

The reversal should only affect the nodes between positions left and right (inclusive), while keeping the rest of the list unchanged. The nodes before position left and after position right should remain in their original order and properly connected to the reversed portion.

The solution uses a dummy node technique to handle edge cases and performs the reversal by:

1. First finding the node just before position left (called pre)
2. Then reversing the connections between nodes from position left to right
3. Finally reconnecting the reversed portion back to the rest of the list

The algorithm tracks pointers p (pointing to the node before the reversal section) and q (pointing to the first node in the reversal section), then reverses the required portion and reconnects everything properly.

Intuition

When we need to reverse a portion of a linked list, the key insight is that we need to handle three distinct parts: the nodes before the reversal section, the nodes within the reversal section, and the nodes after the reversal section.

Think of it like rearranging a chain of beads where you only want to reverse a middle section. You need to:

1. Remember where the section starts and ends
2. Detach the section temporarily
3. Reverse the section
4. Reattach it back to the chain

The challenge with linked lists is that we can only traverse forward, so we need to carefully track our positions. This leads us to realize we need:

• A pointer to the node just before the reversal starts (to reconnect later)
• A pointer to the first node of the section to be reversed (which will become the last node after reversal)
• A way to reverse the nodes in between

The reversal process itself follows the standard linked list reversal pattern: for each node in the section, we reverse its next pointer to point to the previous node instead of the next one. We iterate through right - left + 1 nodes to cover the entire section.

Using a dummy node simplifies edge cases, especially when left = 1 (reversing from the head). Without it, we'd need special logic to handle changing the head of the list.

The variables p and q serve as anchors: p marks the node before the reversal section, and q marks the first node of the reversal section (which becomes the last after reversal). After reversing, we connect p.next to the new first node of the reversed section and q.next to the node after the reversed section.

Learn more about Linked List patterns.

Solution Approach

The implementation uses a simulation approach with pointer manipulation to reverse the specified portion of the linked list.

Step 1: Setup dummy node and initial pointer

dummy = ListNode(0, head)
pre = dummy

We create a dummy node pointing to head to handle edge cases uniformly. The pointer pre will eventually point to the node just before position left.

Step 2: Navigate to the starting position

for _ in range(left - 1):
    pre = pre.next

We move pre forward left - 1 times to position it at the node just before the reversal section starts.

Step 3: Initialize reversal pointers

p, q = pre, pre.next
cur = q

• p stores the reference to the node before the reversal section
• q stores the reference to the first node of the reversal section (will become the last after reversal)
• cur is our working pointer that traverses through the section to be reversed

Step 4: Reverse the specified section

for _ in range(right - left + 1):
    t = cur.next
    cur.next = pre
    pre, cur = cur, t

This loop reverses right - left + 1 nodes:

• t temporarily stores the next node
• cur.next = pre reverses the current node's pointer to point backward
• pre, cur = cur, t advances both pointers for the next iteration

After this loop:

• pre points to what becomes the new first node of the reversed section
• cur points to the node immediately after the reversed section

Step 5: Reconnect the reversed section

p.next = pre
q.next = cur

• p.next = pre connects the node before the reversal to the new first node of the reversed section
• q.next = cur connects the new last node of the reversed section to the rest of the list

Step 6: Return the result

return dummy.next

Returns the head of the modified list, which is dummy.next.

The time complexity is O(n) where n is the number of nodes, as we traverse the list once. The space complexity is O(1) as we only use a constant amount of extra pointers.

Example Walkthrough

Let's walk through the algorithm with a concrete example:

• Input list: 1 -> 2 -> 3 -> 4 -> 5
• left = 2, right = 4
• Expected output: 1 -> 4 -> 3 -> 2 -> 5

Initial Setup:

dummy -> 1 -> 2 -> 3 -> 4 -> 5
pre = dummy

Step 1: Navigate to position before left Move pre forward left - 1 = 1 time:

dummy -> 1 -> 2 -> 3 -> 4 -> 5
         ^
        pre

Step 2: Set up reversal pointers

dummy -> 1 -> 2 -> 3 -> 4 -> 5
         ^    ^
         p    q,cur

• p = pre (points to node 1)
• q = pre.next (points to node 2, first node to reverse)
• cur = q (working pointer, starts at node 2)

Step 3: Reverse the section (3 iterations for positions 2-4)

Iteration 1:

• Save t = cur.next (node 3)
• Set cur.next = pre (node 2 now points to node 1)
• Move pointers: pre = cur (node 2), cur = t (node 3)

State: 1 <- 2    3 -> 4 -> 5
            ^    ^
           pre  cur

Iteration 2:

• Save t = cur.next (node 4)
• Set cur.next = pre (node 3 now points to node 2)
• Move pointers: pre = cur (node 3), cur = t (node 4)

State: 1 <- 2 <- 3    4 -> 5
                 ^    ^
                pre  cur

Iteration 3:

• Save t = cur.next (node 5)
• Set cur.next = pre (node 4 now points to node 3)
• Move pointers: pre = cur (node 4), cur = t (node 5)

State: 1 <- 2 <- 3 <- 4    5
                      ^    ^
                     pre  cur

Step 4: Reconnect the reversed section Remember: p still points to node 1, q still points to node 2

• p.next = pre: Connect node 1 to node 4 (new first of reversed section)
• q.next = cur: Connect node 2 to node 5 (node after reversed section)

Final: dummy -> 1 -> 4 -> 3 -> 2 -> 5

The portion from position 2 to 4 has been successfully reversed while maintaining all connections!

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm traverses the linked list at most once. Breaking down the operations:

• The first loop runs left - 1 times to position the pre pointer before the reversal section
• The second loop runs right - left + 1 times to reverse the nodes between positions left and right
• Total iterations: (left - 1) + (right - left + 1) = right operations

Since right ≤ n where n is the length of the linked list, the time complexity is O(n).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• A dummy node to simplify edge cases
• A fixed number of pointer variables (dummy, pre, p, q, cur, t)

These variables don't scale with the input size, resulting in O(1) space complexity. The reversal is performed in-place by modifying the existing linked list's pointers without creating any new nodes or using recursion.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Errors in Pointer Navigation

One of the most common mistakes is incorrectly calculating how many steps to move the before_reverse pointer. Developers often forget that positions are 1-indexed, not 0-indexed.

Incorrect approach:

# Wrong: Moving 'left' times instead of 'left - 1'
for _ in range(left):  # This goes too far!
    before_reverse = before_reverse.next

Why it fails: If left = 2, we want before_reverse to point to the 1st node (the node before position 2). Moving left times would place it at the 2nd node instead.

Correct approach:

# Correct: Move exactly 'left - 1' times
for _ in range(left - 1):
    before_reverse = before_reverse.next

2. Incorrect Loop Count for Reversal

Another frequent error is reversing the wrong number of nodes. The reversal should include both left and right positions (inclusive).

Incorrect approach:

# Wrong: Only reverses 'right - left' nodes (missing one)
for _ in range(right - left):  # Off by one!
    next_temp = current.next
    current.next = prev
    prev = current
    current = next_temp

Why it fails: If reversing from position 2 to 4, we need to reverse 3 nodes (positions 2, 3, and 4), which is right - left + 1 = 4 - 2 + 1 = 3 nodes.

Correct approach:

# Correct: Reverse exactly 'right - left + 1' nodes
for _ in range(right - left + 1):
    next_temp = current.next
    current.next = prev
    prev = current
    current = next_temp

3. Creating Cycles When Reconnecting

A subtle but critical error occurs when reconnecting the reversed section. If not done carefully, you can create a cycle in the linked list.

Incorrect approach:

# Wrong: Reconnecting before properly breaking old connections
before_reverse.next = prev
# first_reversed.next still points to its old next node, creating a cycle!

Why it fails: After reversal, first_reversed (which becomes the last node of the reversed section) still has its next pointer pointing backward into the reversed section, creating a cycle.

Correct approach:

# Correct: Ensure both connections are updated
before_reverse.next = prev  # Connect to new first of reversed section
first_reversed.next = current  # Connect last of reversed section to remaining list

4. Not Handling Edge Cases Properly

Failing to handle edge cases when left = 1 (reversing from the head) is common when not using a dummy node.

Incorrect approach without dummy node:

# Wrong: Doesn't handle left = 1 case
before_reverse = None
for i in range(left - 1):
    if i == 0:
        before_reverse = head
    else:
        before_reverse = before_reverse.next  # Crashes when before_reverse is None!

Correct approach with dummy node:

# Correct: Dummy node elegantly handles all cases
dummy = ListNode(0, head)
before_reverse = dummy
for _ in range(left - 1):
    before_reverse = before_reverse.next
# Works even when left = 1

Prevention Tips:

1. Always use a dummy node to simplify edge case handling
2. Draw diagrams to visualize pointer movements and connections
3. Test with minimal examples like left = 1, right = n, and left = right
4. Trace through the algorithm step-by-step with a simple example before coding
5. Remember positions are 1-indexed, not 0-indexed, when calculating movements