# Reverse Linked List II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/reverse-linked-list-ii)
Canonical: https://scaleengineer.com/dsa/problems/reverse-linked-list-ii
**Data structures:** Linked List
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nutanix](https://scaleengineer.com/companies/nutanix), [Nvidia](https://scaleengineer.com/companies/nvidia), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [Disney](https://scaleengineer.com/companies/disney), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [Revolut](https://scaleengineer.com/companies/revolut)
---
## Problem
Given the `head` of a singly linked list and two integers `left` and `right` where `left <= right`, reverse the nodes of the list from position `left` to position `right`, and return _the reversed list_.

**Example 1:**

![](https://assets.glich.co/dsa/reverse-linked-list-ii/image0.jpg) 

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

**Example 2:**

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

**Constraints:**

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

**Follow up:** Could you do it in one pass?

# Approaches
## Store in Array and Replace Values
This approach involves converting the linked list into an array of values, reversing the specified sub-array, and then iterating through the linked list again to update the node values from the modified array.
**Time:** O(N) · **Space:** O(N)
**Pros:** Conceptually simple and easy to implement.; Avoids the complexity of direct pointer manipulation in a linked list.
**Cons:** Requires O(N) extra space to store the node values, which is inefficient for large lists.; Requires two full passes over the data: one to build the array and another to update the list values.; It only modifies the values within the nodes, not the actual pointers. This might not be acceptable if the nodes contain more complex data or if pointer manipulation is a requirement.
### Explanation
This is a straightforward but less efficient approach. The core idea is to avoid complex pointer manipulation by offloading the reversal logic to a more convenient data structure, an array.

- First, we traverse the entire linked list and store the value of each node in a dynamic array (like `ArrayList` in Java).
- Once all values are in the array, we reverse the portion of the array from index `left - 1` to `right - 1`. This can be done using a standard two-pointer swapping technique.
- Finally, we traverse the linked list a second time from the head. In this traversal, we update the value of each node with the corresponding value from our modified array.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || left == right) {
            return head;
        }

        // 1. Copy list values to an ArrayList
        List<Integer> values = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            values.add(current.val);
            current = current.next;
        }

        // 2. Reverse the sublist of values
        int l = left - 1;
        int r = right - 1;
        while (l < r) {
            int temp = values.get(l);
            values.set(l, values.get(r));
            values.set(r, temp);
            l++;
            r--;
        }

        // 3. Update the linked list with the new values
        current = head;
        for (int val : values) {
            current.val = val;
            current = current.next;
        }

        return head;
    }
}
```
### Algorithm
- If `head` is null or `left == right`, there's nothing to reverse, so return `head`.
- Create an `ArrayList<Integer>` to store the values of the nodes.
- Traverse the linked list from the `head` with a pointer, `current`, and add the value of each node (`current.val`) to the `ArrayList`.
- After the list is fully traversed, the `ArrayList` contains all node values in order.
- Reverse the sub-array within the `ArrayList` from index `left - 1` to `right - 1`. This can be done with a two-pointer approach, swapping elements from both ends of the sub-array until the pointers meet.
- Reset the `current` pointer back to the `head` of the linked list.
- Iterate through the `ArrayList` from the beginning, and for each value, update the corresponding node in the linked list: `current.val = arraylist.get(i)`. Move `current` to the next node.
- Return the original `head` of the list, which now contains the modified values.

## Recursive In-place Reversal
This approach uses recursion to solve the problem. The main idea is to peel off nodes one by one until we reach the `left`-th position. Once there, we use another recursive helper function to reverse `right - left + 1` nodes.
**Time:** O(N) · **Space:** O(N)
**Pros:** Provides an elegant and concise recursive structure that mirrors the problem's definition.; Manipulates pointers directly, preserving the original node objects.
**Cons:** Uses O(N) space for the recursion call stack in the worst case, which is suboptimal compared to the iterative solution.; Can be harder to reason about and debug than an iterative approach for those not comfortable with recursion.; The use of a shared `successor` variable (as a class member or passed by reference) can be considered a side effect, which can make the code less clean.
### Explanation
This approach leverages the call stack to manage the state of the reversal. It's an elegant way to think about the problem by breaking it down into smaller, self-similar subproblems.

The solution is broken down into two parts:
1. A main recursive function `reverseBetween(head, left, right)` that navigates to the start of the sublist to be reversed.
2. A helper recursive function `reverseN(head, n)` that reverses the first `n` nodes of a given list.

The `reverseBetween` function decrements `left` and `right` and calls itself on `head.next` until `left` becomes 1. This means we have reached the starting node for reversal. When `left` is 1, it calls `reverseN(head, right)` to perform the actual reversal of `right` nodes.

The `reverseN` function works by recursively reversing `n-1` nodes from `head.next`. On the way back up the call stack, it reverses the pointers. A key detail is to save the `(n+1)`-th node (the successor) before the recursion, so the reversed sublist can be correctly linked back to the rest of the list.

```java
class Solution {
    private ListNode successor = null;

    // Reverses the first n nodes of the list starting at head
    private ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            // Base case: reached the end of the sublist to reverse
            successor = head.next; // Save the node after the sublist
            return head;
        }
        // Recurse on the rest of the list
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        // Connect the reversed part to the successor
        head.next = successor;
        return last;
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            // If reversal starts from the head, just reverse the first 'right' nodes
            return reverseN(head, right);
        }
        // Recurse until we reach the starting point of reversal
        // The subproblem is to reverse the list starting from head.next
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }
}
```
### Algorithm
- The main function `reverseBetween(head, left, right)` serves as the entry point.
- **Base Case:** If `left == 1`, it means the reversal starts from the current `head`. We then call a helper function, `reverseN(head, right)`, which is responsible for reversing the first `right` nodes of a list.
- **Recursive Step:** If `left > 1`, the current `head` is not part of the sublist to be reversed. We keep it in place and make a recursive call on the rest of the list: `head.next = reverseBetween(head.next, left - 1, right - 1)`. This effectively moves our 'window' of reversal one step down the list.
- The helper function `reverseN(head, n)` reverses the first `n` nodes:
  - It uses a class-level variable `successor` to keep track of the node that comes after the sublist being reversed.
  - **Base Case:** If `n == 1`, we've reached the end of the sublist. We store `head.next` in `successor` and return `head`.
  - **Recursive Step:** It calls `reverseN(head.next, n - 1)`. When this call returns, it provides the new head of the reversed tail (`last`). We then rewire the pointers: `head.next.next` points back to `head`, and `head.next` points to the saved `successor`.
  - It returns `last`, which propagates the new head of the reversed section up the call stack.

## Iterative In-place Reversal (One Pass)
This is the most optimal approach, solving the problem in a single pass with constant extra space. It involves careful pointer manipulation to reverse the sublist directly within the original list.
**Time:** O(N) · **Space:** O(1)
**Pros:** Optimal O(1) space complexity as it only uses a few extra pointers.; Highly efficient single-pass solution with O(N) time complexity.; Handles all edge cases gracefully, especially with the use of a dummy node.
**Cons:** The pointer manipulation can be complex and non-intuitive to understand and implement correctly without careful visualization.
### Explanation
This iterative approach is the standard and most efficient solution. It directly manipulates the node pointers in-place to achieve the reversal.

- We use a `dummy` node to simplify edge cases, such as when the reversal starts at the head of the list (`left = 1`). The `dummy` node points to the original `head`.
- First, we iterate `left - 1` times to find the node just before the sublist to be reversed. Let's call this `pre_left`.
- We then identify the start of our sublist, `current = pre_left.next`. This `current` node will act as a pivot and will become the tail of the reversed sublist after all operations.
- We then loop `right - left` times. In each iteration, we take the node immediately following `current` (let's call it `node_to_move`) and move it to become the new first node of the sublist (i.e., right after `pre_left`).

Let's trace `[1,2,3,4,5]`, `left=2`, `right=4`:
- Initial: `dummy -> 1 -> 2 -> 3 -> 4 -> 5`. `pre_left` is at `1`, `current` is at `2`.
- Iteration 1 (move `3`): `node_to_move` is `3`. The list becomes `dummy -> 1 -> 3 -> 2 -> 4 -> 5`.
- Iteration 2 (move `4`): `node_to_move` is `4`. The list becomes `dummy -> 1 -> 4 -> 3 -> 2 -> 5`.

After the loop, the sublist is reversed, and all connections are correctly updated. We return `dummy.next`.

```java
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || left == right) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 1. Reach node at position `left - 1`
        ListNode pre_left = dummy;
        for (int i = 0; i < left - 1; i++) {
            pre_left = pre_left.next;
        }

        // 2. `current` points to the node at position `left`
        ListNode current = pre_left.next;

        // 3. Reverse the sublist
        for (int i = 0; i < right - left; i++) {
            ListNode node_to_move = current.next;
            current.next = node_to_move.next;
            node_to_move.next = pre_left.next;
            pre_left.next = node_to_move;
        }

        return dummy.next;
    }
}
```
### Algorithm
- Create a `dummy` node and set `dummy.next = head`. This simplifies handling the edge case where `left = 1`.
- Create a pointer `pre_left` and initialize it to `dummy`.
- Move `pre_left` forward `left - 1` times. After the loop, `pre_left` will be at the node just before the sublist to be reversed.
- Initialize `current = pre_left.next`. This `current` pointer marks the start of the sublist to be reversed and will eventually become its tail.
- Loop `right - left` times. This is the core of the reversal:
  - a. Let `node_to_move = current.next`. This is the node we will move to the front of the reversed section.
  - b. Detach `node_to_move` from its current position by setting `current.next = node_to_move.next`.
  - c. Prepend `node_to_move` to the reversed part by setting `node_to_move.next = pre_left.next`.
  - d. Update the link from the preceding part of the list by setting `pre_left.next = node_to_move`.
- After the loop completes, the sublist from `left` to `right` is reversed and correctly linked with the rest of the list.
- Return `dummy.next`, which is the head of the modified list.

# Solutions
### CSharp

```csharp
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode ReverseBetween ( ListNode head , int left , int right ) { if ( head . next == null || left == right ) { return head ; } ListNode dummy = new ListNode ( 0 , head ); ListNode pre = dummy ; for ( int i = 0 ; i < left - 1 ; ++ i ) { pre = pre . next ; } ListNode p = pre ; ListNode q = pre . next ; ListNode cur = q ; for ( int i = 0 ; i < right - left + 1 ; ++ i ) { ListNode t = cur . next ; cur . next = pre ; pre = cur ; cur = t ; } p . next = pre ; q . next = cur ; return dummy . next ; } }
```

### Java

```java
import java.util.Stack ; public class Reverse_Linked_List_II { /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution_optimize { public ListNode reverseBetween ( ListNode head , int m , int n ) { ListNode dummy = new ListNode ( 0 ); ListNode prev = dummy ; // I missed this one prev . next = head ; ListNode p = head ; for ( int i = 1 ; i < m ; i ++) { prev = p ; p = p . next ; } // @note:@memorize: now p is pointing to m-th node ListNode originalFirst = p ; for ( int i = m ; i < n ; i ++) { ListNode currentHead = prev . next ; ListNode futureHead = originalFirst . next ; // swap // prev.next = currentHead.next; prev . next = futureHead ; // currentHead.next = futureHead.next; originalFirst . next = futureHead . next ; futureHead . next = currentHead ; } return dummy . next ; } } public class Solution { public ListNode reverseBetween ( ListNode head , int m , int n ) { if ( m > n ) { return reverseBetween ( head , n , m ); } int diff = n - m ; if ( diff == 0 ) { return head ; } ListNode p1 = head ; // set diff for both pointers // @note: corner case: n-m > list-length while ( diff > 0 && p1 != null ) { p1 = p1 . next ; diff --; } ListNode dummy = new ListNode ( 0 ); dummy . next = head ; ListNode prev = dummy ; ListNode p2 = head ; int mm = m ; while ( mm - 1 > 0 ) { prev = prev . next ; p1 = p1 . next ; p2 = p2 . next ; mm --; } ListNode nextRecord = p1 . next ; diff = n - m ; // start reverse from p1 to p2 // 1->2->3->4->5 Stack < ListNode > sk = new Stack <>(); while ( p2 != p1 . next ) { // @note: here, when p1==p2 should enter loop sk . push ( p2 ); p2 = p2 . next ; } while (! sk . isEmpty ()) { prev . next = sk . pop (); prev = prev . next ; } prev . next = nextRecord ; return dummy . next ; } } } ############ /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseBetween ( ListNode head , int left , int right ) { if ( head . next == null || left == right ) { return head ; } ListNode dummy = new ListNode ( 0 , head ); ListNode pre = dummy ; for ( int i = 0 ; i < left - 1 ; ++ i ) { pre = pre . next ; } ListNode p = pre ; ListNode q = pre . next ; ListNode cur = q ; for ( int i = 0 ; i < right - left + 1 ; ++ i ) { ListNode t = cur . next ; cur . next = pre ; pre = cur ; cur = t ; } p . next = pre ; q . next = cur ; return dummy . next ; } }
```

### JavaScript

```javascript
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} left * @param {number} right * @return {ListNode} */ var reverseBetween =
  function (head, left, right) {
    if (!head.next || left == right) {
      return head;
    }
    const dummy = new ListNode(0, head);
    let pre = dummy;
    for (let i = 0; i < left - 1; ++i) {
      pre = pre.next;
    }
    const p = pre;
    const q = pre.next;
    let cur = q;
    for (let i = 0; i < right - left + 1; ++i) {
      const t = cur.next;
      cur.next = pre;
      pre = cur;
      cur = t;
    }
    p.next = pre;
    q.next = cur;
    return dummy.next;
  };

```

### Python

```python
# 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 # +1, so when for loop done, 'cur' is at right's next node for _ in range ( right - left + 1 ): t = cur . next cur . next = pre pre , cur = cur , t p . next = pre # p,q did not change by the for loop, but now pre at right(or called m) node, cur at right+1 node q . next = cur return dummy . next ############ class Solution_optimize : def reverseBetween ( self , head : ListNode , m : int , n : int ) -> ListNode : dummy = ListNode ( 0 ) prev = dummy prev . next = head p = head for i in range ( 1 , m ): prev = p p = p . next original_first = p # this is anchor node always pointing to the next-to-be-swapped for i in range ( m , n ): current_head = prev . next future_head = original_first . next prev . next = future_head original_first . next = future_head . next future_head . next = current_head return dummy . next ############ # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution ( object ): def reverseBetween ( self , head , m , n ): """ :type head: ListNode :type m: int :type n: int :rtype: ListNode """ def reverse ( root , prep , k ): cur = root pre = None next = None while cur and k > 0 : next = cur . next cur . next = pre pre = cur cur = next k -= 1 root . next = next prep . next = pre return pre dummy = ListNode ( - 1 ) dummy . next = head k = 1 p = dummy start = None while p : if k == m : start = p if k == n + 1 : reverse ( start . next , start , n - m + 1 ) return dummy . next k += 1 p = p . next
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/reverse-linked-list-ii/ // Time: O(N) // Space: O(1) class Solution { public: ListNode * reverseBetween ( ListNode * head , int m , int n ) { ListNode dummy , * p = & dummy ; dummy . next = head ; for ( int i = 1 ; i < m ; ++ i ) p = p -> next ; auto q = p -> next , tail = q ; for ( int i = m ; i <= n ; ++ i ) { auto node = q ; q = q -> next ; node -> next = p -> next ; p -> next = node ; } tail -> next = q ; return dummy . next ; } };
```