How do you solve Reverse Linked List II on LeetCode?

Reverse Linked List II (LeetCode #92) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Reversing a linked list can be done in place, which is more efficient.

What is the brute force solution for Reverse Linked List II?

The brute force approach for Reverse Linked List II is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves reversing the sublist by first extracting it, reversing it, and then reattaching it to the original list. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Reverse Linked List II?

Reverse Linked List II uses the following concepts: Linked List. The recommended patterns to study are: Two Pointers, In-Place Reversal.

What are the interview tips for Reverse Linked List II?

Think about edge cases and how they affect your pointers. Practice explaining your thought process as you code. Consider the space and time complexity of your solution.

What are common mistakes when solving Reverse Linked List II?

Not handling edge cases like when left equals right. Failing to properly reconnect the reversed sublist to the original list.

#92

Reverse Linked List II

Medium

Linked ListTwo PointersIn-Place Reversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal approach reverses the sublist in place without needing to extract it first. This reduces the time complexity significantly and allows us to do it in one pass.

⚙️

Algorithm

3 steps

1Step 1: Use a dummy node to simplify edge cases and find the node just before the 'left' position.
2Step 2: Reverse the nodes between 'left' and 'right' using a loop.
3Step 3: Reconnect the reversed sublist to the original list.

solution.py21 lines

1# Full working Python code
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7def reverseBetween(head: ListNode, left: int, right: int) -> ListNode:
8    if not head or left == right:
9        return head
10    dummy = ListNode(0, head)
11    prev = dummy
12    for _ in range(left - 1):
13        prev = prev.next
14    curr = prev.next
15    tail = curr
16    for _ in range(right - left):
17        temp = curr.next
18        curr.next = temp.next
19        temp.next = prev.next
20        prev.next = temp
21    return dummy.next

ℹ

Complexity note: The time complexity is O(n) because we traverse the list only once to find the nodes and reverse them in place, and the space complexity is O(1) since we are using a constant amount of extra space.

1Reversing a linked list can be done in place, which is more efficient.
2Using a dummy node simplifies edge cases when modifying the head of the list.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.