LeetCode 92: Reverse Linked List II

Problem Restatement

We are given the head of a singly linked list and two integers:

left
right

The positions are 1-indexed.

We need to reverse the nodes from position left to position right, inclusive, and return the modified list.

Only that middle section should be reversed. The nodes before left and after right must stay in their original order.

The official statement asks us to reverse the nodes from position left to position right and return the reversed list. Example: [1,2,3,4,5], left = 2, right = 4 becomes [1,4,3,2,5].

Input and Output

Function shape:

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

Examples

Example 1:

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

The section to reverse is:

2 -> 3 -> 4

After reversal:

4 -> 3 -> 2

The final list is:

[1, 4, 3, 2, 5]

Example 2:

head = [5]
left = 1
right = 1

There is only one node, so reversing the range changes nothing.

Answer:

[5]

First Thought: Copy Values Into an Array

A simple method is to copy all node values into an array.

Then reverse the slice:

values[left - 1:right]

Then write the values back into the linked list.

This works, but it does not reverse the linked list nodes directly. It also uses extra memory.

We can solve it in-place by rewiring next pointers.

Key Insight

The list has three parts:

before left
left ... right
after right

Only the middle part changes direction.

A dummy node helps handle the case where left = 1.

dummy -> head

We first move a pointer prev to the node just before position left.

Then we reverse the next right - left + 1 nodes.

Finally, we reconnect the reversed section to the rest of the list.

Algorithm

Create:

dummy = ListNode(0, head)

Move prev to the node before the reversed section:

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

Now:

Reverse exactly right - left + 1 nodes.

After reversal:

1. prev.next should point to the new head of the reversed section.
2. tail.next should point to the node after the reversed section.
3. Return dummy.next.

Walkthrough

Use:

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

Add dummy:

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

Move prev to the node before position 2:

prev = node 1

The section starts at node 2.

prev -> 2 -> 3 -> 4 -> 5

Now reverse three nodes:

2 -> 3 -> 4

During reversal, the links become:

4 -> 3 -> 2

The node 2 becomes the tail of the reversed section.

Reconnect:

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

Return:

[1, 4, 3, 2, 5]

Correctness

The algorithm first places prev immediately before position left. Therefore, prev.next is the first node that must be reversed.

The reversal loop runs exactly right - left + 1 times, so it reverses exactly the nodes in the target range and no others.

During the reversal, cur moves through the target section, and new_head becomes the head of the reversed section. The original first node of the section is saved as tail; after reversal, that node becomes the last node of the reversed section.

The node after the reversed range is saved as cur when the reversal loop finishes. Setting:

tail.next = cur

connects the reversed section to the suffix of the original list.

Setting:

prev.next = new_head

connects the prefix of the original list to the reversed section.

All nodes before left are untouched. All nodes after right are untouched. The middle section is reversed. Therefore, the returned list is correct.

Complexity

Let:

n = number of nodes

Implementation

# 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]:
        dummy = ListNode(0, head)

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

        tail = prev.next
        cur = prev.next
        new_head = None

        for _ in range(right - left + 1):
            nxt = cur.next
            cur.next = new_head
            new_head = cur
            cur = nxt

        prev.next = new_head
        tail.next = cur

        return dummy.next

Code Explanation

The dummy node handles reversal starting at the head:

dummy = ListNode(0, head)

Move prev to the node before left:

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

Save the first node of the section:

tail = prev.next

This node becomes the tail after reversal.

Start reversing from the same node:

cur = prev.next
new_head = None

Reverse exactly the target section:

for _ in range(right - left + 1):
    nxt = cur.next
    cur.next = new_head
    new_head = cur
    cur = nxt

After the loop:

Reconnect the prefix:

prev.next = new_head

Reconnect the suffix:

tail.next = cur

Return the real head:

return dummy.next

Testing

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

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

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

    return dummy.next

def to_list(head):
    values = []

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

    return values

def check(values, left, right, expected):
    s = Solution()
    head = build_list(values)
    result = s.reverseBetween(head, left, right)
    assert to_list(result) == expected

def run_tests():
    check([1, 2, 3, 4, 5], 2, 4, [1, 4, 3, 2, 5])
    check([5], 1, 1, [5])
    check([1, 2, 3], 1, 2, [2, 1, 3])
    check([1, 2, 3], 2, 3, [1, 3, 2])
    check([1, 2, 3], 1, 3, [3, 2, 1])
    check([1, 2], 1, 1, [1, 2])

    print("all tests passed")

run_tests()

Test meaning: