#92

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Reverse Linked List II

Reverse a segment of a singly linked list from position left to right using precise pointer manipulation techniques.

Problem Statement

Given the head of a singly linked list and two integers, left and right, reverse all nodes from the left-th to the right-th position, and return the modified list. The reversal must be done in-place, using pointer manipulation without creating new nodes.

For example, given head = [1,2,3,4,5], left = 2, right = 4, the nodes 2,3,4 should be reversed resulting in [1,4,3,2,5]. If left equals right, the list remains unchanged. Constraints ensure that 1 <= left <= right <= n, with n up to 500 nodes.

Examples

Example 1

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

Output: [1,4,3,2,5]

Example details omitted.

Example 2

Input: head = [5], left = 1, right = 1

Output: [5]

Example details omitted.

Constraints

The number of nodes in the list is n.
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

Solution Approach

Use a dummy node for edge handling

Introduce a dummy node before the head to simplify reversing when left is 1. Move a pointer to the node just before the left-th node to start reconnection after reversal.

Iteratively reverse the sublist

Perform in-place reversal by iterating from left to right, adjusting next pointers for each node. Carefully track previous, current, and next nodes to avoid breaking the list.

Reconnect the reversed segment

After reversing, connect the node before the left-th position to the new head of the reversed sublist, and the tail of the reversed sublist to the node after right. Return dummy.next as the new head.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each node is visited at most once during traversal and reversal. Space complexity is O(1) because the reversal is done in-place with only a few extra pointers regardless of list size.

What Interviewers Usually Probe

Checks if the candidate handles edge cases like left == 1 or left == right.
Looks for in-place pointer manipulation without using extra arrays or stacks.
Monitors how well the candidate maintains connections before and after the reversed sublist.

Common Pitfalls or Variants

Common pitfalls

Failing to handle the case where the reversal starts at the head node.
Incorrectly reconnecting the reversed sublist to the remaining list, breaking links.
Using extra memory instead of performing true in-place reversal.

Follow-up variants

Reverse nodes in groups of k instead of a single sublist, extending pointer manipulation skills.
Reverse a sublist with possible cycles in the linked list, requiring cycle detection.
Reverse only nodes with even values between left and right, combining conditional logic with pointer manipulation.

FAQ

What is the best approach to reverse a sublist in 'Reverse Linked List II'?

Use a dummy node, locate the node before left, iteratively reverse nodes from left to right, then reconnect the reversed segment to the rest of the list.

Can I use extra arrays or stacks for this problem?

While possible, optimal solutions use in-place pointer manipulation to meet the problem's space efficiency requirements.

How do I handle the edge case where left equals right?

No reversal is needed; the list remains unchanged, but your code should still correctly return the original head.

What pointers are critical during the reversal?

Track the previous node before the sublist, the current node being reversed, and the next node to maintain proper connections.

How can I verify the reversed segment is correct?

Walk through the list after reversal, checking that nodes between left and right are reversed and all other nodes maintain original order.

terminal

Solution

Solution 1: Simulation

Define a dummy head node `dummy`, pointing to the head node `head` of the linked list. Then define a pointer `pre` pointing to `dummy`. Start traversing the linked list from the dummy head node. When you traverse to the `left` node, point `pre` to this node. Then start traversing `right - left + 1` times from this node, and insert the nodes you traverse into the back of `pre`. Finally, return `dummy.next`.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

# 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 head.next is None or left == right:
            return head
        dummy = ListNode(0, head)
        pre = dummy
        for _ in range(left - 1):
            pre = pre.next
        p, q = pre, pre.next
        cur = q
        for _ in range(right - left + 1):
            t = cur.next
            cur.next = pre
            pre, cur = cur, t
        p.next = pre
        q.next = cur
        return dummy.next

Continue Practicing

#86 partition list #83 remove duplicates from sorted list #82 remove duplicates from sorted list ii