LeetCode 92 - Reverse Linked List II

This problem asks us to reverse only a specific portion of a singly linked list, rather than reversing the entire list. We are given the head of a linked list and two integer positions, left and right, where left <= right.

leetcodemediumlinked-list

LeetCode Problem 92

Difficulty: 🟡 Medium
Topics: Linked List

Solution

Problem Understanding

This problem asks us to reverse only a specific portion of a singly linked list, rather than reversing the entire list. We are given the head of a linked list and two integer positions, left and right, where left <= right. The goal is to reverse all nodes starting at position left and ending at position right, while leaving the rest of the linked list unchanged.

In other words, imagine cutting out a continuous segment of the linked list, reversing the order of the nodes in that segment, and then reconnecting it back into the original list. The positions are 1-indexed, meaning the first node is position 1, the second node is position 2, and so on.

For example, consider:

1 -> 2 -> 3 -> 4 -> 5

If left = 2 and right = 4, the sublist:

2 -> 3 -> 4

must be reversed into:

4 -> 3 -> 2

and reattached:

1 -> 4 -> 3 -> 2 -> 5

The input consists of:

  • head, the first node of a singly linked list
  • left, the starting position of the reversal
  • right, the ending position of the reversal

The expected output is the head of the modified linked list after the specified sublist has been reversed.

The constraints tell us that the list contains between 1 and 500 nodes, which is relatively small. This means even less efficient solutions could work within limits, but the follow-up specifically asks whether we can solve it in one pass, which strongly hints that an optimal in-place linked list manipulation approach is expected.

Several edge cases are important to identify upfront. If left == right, there is nothing to reverse, since the segment contains only one node. Reversing from the first node (left = 1) is tricky because the head itself may change after reversal. Reversing the tail portion of the list requires careful reconnection of pointers so the reversed segment still links correctly to the remainder of the list. A naive implementation can easily lose references to nodes if pointer updates are done in the wrong order.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to first convert the linked list into an array of node values. Once the values are stored in an array, reversing the subarray between left - 1 and right - 1 becomes simple using standard array operations. After the reversal, we can rebuild the linked list or overwrite node values in the original list.

This works because arrays support direct indexing, making subarray reversal easy. Since the list size is small, performance is acceptable for the given constraints.

However, this approach is not ideal because it uses extra memory and does not take advantage of linked list structure. More importantly, the follow-up explicitly asks for a one-pass solution, which suggests we should manipulate pointers directly instead of copying values.

Optimal Approach

The key observation is that we can reverse the sublist in place by carefully rewiring pointers during a single traversal of the linked list.

The main challenge is reconnecting the reversed segment with the unchanged parts of the list. We need to keep track of:

  • The node immediately before the reversal starts
  • The first node of the sublist being reversed
  • The node immediately after the reversal ends

A useful trick is to introduce a dummy node before the head. This simplifies handling cases where the reversal starts at position 1, because we always have a node before the reversal segment.

Instead of fully reversing the sublist using a traditional pointer reversal loop, we can repeatedly move nodes to the front of the sublist. This technique performs the reversal in one traversal and avoids extra memory allocation.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Convert linked list to array, reverse segment, rebuild or overwrite
Optimal O(n) O(1) Reverse pointers in place using a dummy node and one pass

Algorithm Walkthrough

The optimal algorithm reverses the linked list segment in place using pointer manipulation.

  1. Handle trivial cases

If the list is empty or left == right, return the original list immediately. No reversal is needed. 2. Create a dummy node

Create a dummy node whose next points to head.

This simplifies edge cases where the reversal starts at the first node because we always have a valid "previous" node.

Example:

dummy -> 1 -> 2 -> 3 -> 4 -> 5
  1. Move to the node before the reversal starts

Traverse the list until reaching position left - 1.

This node is important because after reversal, it must connect to the new front of the reversed sublist.

For:

left = 2

we stop at node 1. 4. Initialize reversal pointers

Let:

  • prev_node = node before reversal
  • current = first node of the segment

Example:

dummy -> 1 -> 2 -> 3 -> 4 -> 5
           ^
      prev_node
                ^
              current
  1. Reverse by front insertion

Repeat right - left times:

  • Remove the node after current
  • Insert it immediately after prev_node

Example iteration:

Initial:

1 -> 2 -> 3 -> 4 -> 5

Move 3 in front of 2:

1 -> 3 -> 2 -> 4 -> 5

Then move 4 in front:

1 -> 4 -> 3 -> 2 -> 5
  1. Return the new head

Since the head may have changed, return dummy.next.

Why it works

The algorithm maintains an important invariant: after each iteration, the nodes between left and the current processed position are already reversed and properly connected to the unchanged portions of the list. The current pointer always marks the tail of the partially reversed segment, while nodes are repeatedly inserted at the front. Because every pointer update preserves connectivity, the list never becomes disconnected, and after right - left iterations the target segment is fully reversed.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseBetween(
        self,
        head: Optional[ListNode],
        left: int,
        right: int
    ) -> Optional[ListNode]:

        if not head or left == right:
            return head

        dummy = ListNode(0)
        dummy.next = head

        prev_node = dummy

        # Move to node before reversal starts
        for _ in range(left - 1):
            prev_node = prev_node.next

        current = prev_node.next

        # Reverse sublist using front insertion
        for _ in range(right - left):
            next_node = current.next
            current.next = next_node.next

            next_node.next = prev_node.next
            prev_node.next = next_node

        return dummy.next

The implementation starts by handling trivial cases where reversal is unnecessary. If the list is empty or left == right, the original head is returned immediately.

A dummy node is then created and connected to the original head. This simplifies pointer handling, especially when the reversal begins at position 1.

The prev_node pointer is moved to the node immediately before the reversal segment. This pointer acts as the anchor point for reconnecting the reversed portion.

The variable current stores the first node of the segment being reversed. During each iteration, the node immediately after current is extracted and inserted at the front of the reversal region. This effectively reverses the order without requiring a separate reversal pass.

Finally, dummy.next is returned because the head of the linked list may have changed.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    if head == nil || left == right {
        return head
    }

    dummy := &ListNode{Next: head}
    prevNode := dummy

    // Move to node before reversal starts
    for i := 0; i < left-1; i++ {
        prevNode = prevNode.Next
    }

    current := prevNode.Next

    // Reverse sublist using front insertion
    for i := 0; i < right-left; i++ {
        nextNode := current.Next

        current.Next = nextNode.Next

        nextNode.Next = prevNode.Next
        prevNode.Next = nextNode
    }

    return dummy.Next
}

The Go implementation follows the same logic as the Python version, but uses pointer syntax explicitly. Since Go does not have None, it uses nil to represent an empty linked list. Pointer manipulation behaves similarly, though dereferencing happens automatically in most cases through field access.

No integer overflow concerns exist here because node values and indices are small and the algorithm performs only pointer operations.

Worked Examples

Example 1

Input:

head = [1,2,3,4,5]
left = 2
right = 4

Initial list:

1 -> 2 -> 3 -> 4 -> 5

After locating the node before reversal:

prev_node = 1
current = 2
Step Operation List State
Initial Start 1 → 2 → 3 → 4 → 5
Iteration 1 Move 3 to front 1 → 3 → 2 → 4 → 5
Iteration 2 Move 4 to front 1 → 4 → 3 → 2 → 5

Final output:

[1,4,3,2,5]

Example 2

Input:

head = [5]
left = 1
right = 1

Since left == right, no reversal is necessary.

Step Action Result
Initial Check condition left == right
Return No modification [5]

Final output:

[5]

Complexity Analysis

Measure Complexity Explanation
Time O(n) We traverse the linked list once, with each node visited at most a constant number of times
Space O(1) Only a few pointer variables are used, no extra data structures are allocated

The time complexity is linear because we first move to the starting point of the reversal and then perform a constant amount of work for each node in the target segment. Even though there are nested-looking operations, each pointer manipulation is constant time.

The space complexity is constant because the algorithm modifies the linked list in place and only uses a fixed number of references regardless of input size.

Test Cases

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

def to_list(head):
    result = []

    while head:
        result.append(head.val)
        head = head.next

    return result

solution = Solution()

# Example 1
head = build_list([1, 2, 3, 4, 5])
assert to_list(solution.reverseBetween(head, 2, 4)) == [1, 4, 3, 2, 5]  # middle sublist reversal

# Example 2
head = build_list([5])
assert to_list(solution.reverseBetween(head, 1, 1)) == [5]  # single node list

# Reverse entire list
head = build_list([1, 2, 3, 4])
assert to_list(solution.reverseBetween(head, 1, 4)) == [4, 3, 2, 1]  # full reversal

# Reverse from head only
head = build_list([1, 2, 3])
assert to_list(solution.reverseBetween(head, 1, 2)) == [2, 1, 3]  # head changes

# Reverse tail portion
head = build_list([1, 2, 3, 4])
assert to_list(solution.reverseBetween(head, 3, 4)) == [1, 2, 4, 3]  # tail reversal

# No-op reversal
head = build_list([1, 2, 3])
assert to_list(solution.reverseBetween(head, 2, 2)) == [1, 2, 3]  # left == right

# Two-node reversal
head = build_list([1, 2])
assert to_list(solution.reverseBetween(head, 1, 2)) == [2, 1]  # minimal non-trivial case

# Larger middle segment
head = build_list([1, 2, 3, 4, 5, 6])
assert to_list(solution.reverseBetween(head, 2, 5)) == [1, 5, 4, 3, 2, 6]  # larger segment
Test Why
[1,2,3,4,5], 2, 4 Validates standard middle reversal
[5], 1, 1 Verifies single-node handling
[1,2,3,4], 1, 4 Ensures full list reversal works
[1,2,3], 1, 2 Tests reversal involving the head
[1,2,3,4], 3, 4 Verifies tail reconnection
[1,2,3], 2, 2 Confirms no changes when left == right
[1,2], 1, 2 Tests smallest meaningful reversal
[1,2,3,4,5,6], 2, 5 Validates larger internal reversal

Edge Cases

One important edge case occurs when left == right. In this scenario, the sublist contains only one node, meaning reversal would have no effect. A buggy implementation might still attempt pointer manipulation and accidentally break the list. The implementation avoids this by immediately returning the original head.

Another critical case is when reversal starts at the head of the list, meaning left = 1. Without careful handling, reconnecting the reversed section becomes difficult because there is no previous node before the head. The dummy node solves this problem elegantly by providing a stable predecessor for all cases.

A third important edge case is reversing the tail portion of the linked list. For example:

1 -> 2 -> 3 -> 4
left = 3
right = 4

After reversal, the list should become:

1 -> 2 -> 4 -> 3

Incorrect pointer updates can easily disconnect the tail or create cycles. The implementation handles this safely because current always remains attached to the unreversed portion, ensuring the remaining nodes are never lost.

A final subtle case is reversing the entire linked list. Since both the beginning and end connections change, implementations without a dummy node often fail to update the head correctly. Returning dummy.next guarantees the correct head is always returned after reversal.