# Topic description

Reverse the linked list from position m to n. Please use one scan to complete the reversal.

illustrate:
1 ≤ m ≤ n ≤ linked list length.

Example:

Input: 1->2->3->4->5->null, M = 2, n = 4
Output: 1->4->3->2->5->null

# ideas

This problem is actually an extension of the algorithm of "recursively inverting a linked list".

Reverse the entire linked list recursively:

```ListNode reverse(ListNode head) {
return last;
}

```

## Reverse the first N nodes of the linked list

This time we implement a function like this:

```// Reverse the first n nodes of the linked list (n < = length of the linked list)
```

For example, for the linked list in the following figure, execute reverseN(head, 3): The solution is similar to reversing the entire linked list, with a little modification:

```ListNode successor = null; // rear drive node

// Reverse the n nodes starting from head and return the new head node
ListNode reverseN(ListNode head, int n) {
if (n == 1) {
// record the n+1th node
}
// Take head.next as the starting point and need to reverse the first n - 1 nodes
ListNode last = reverseN(head.next, n - 1);

// Connect the inverted head node to the next node
return last;
}
```

Specific differences:

1. The base case becomes n == 1, and an element is reversed, which is itself, and the trailing node is recorded.

2. In the original algorithm, we directly set head.next to null, because after the entire linked list is reversed, the original head becomes the last node of the entire linked list. But now the head node is not necessarily the last node after the recursive reversal, so record the successor (the n + 1 th node) of the rear drive, and connect the head after the reversal. OK, if you can understand this function, it is not far from realizing "reversing part of the linked list".

## Reverse part of linked list

Now to solve the problem we posed at the beginning, given an index range [m,n] (indices start at 1), just reverse the list elements in the range.

```ListNode reverseBetween(ListNode head, int m, int n)
```

First of all, if m == 1, it is equivalent to reversing the first n elements from the beginning of the linked list, which is the function we just implemented:

```ListNode reverseBetween(ListNode head, int m, int n) {
// base case
if (m == 1) {
// Equivalent to reversing the first n elements
}
// ...
}
```

What if m != 1 ? If the index of head is regarded as 1, then we want to reverse from the mth element;
What if the index of head.next is treated as 1? Then relative to head.next, the reversed interval should start from the m - 1 th element; then for head.next.next...

Different from iterative thinking, this is recursive thinking, so we can complete the code:

```ListNode reverseBetween(ListNode head, int m, int n) {
// base case
if (m == 1) {
}
// Advance to the start of the reversal to trigger the base case
}
```

At this point, our final big BOSS has been solved.

The idea of ​​recursion is a little harder to understand than the idea of ​​iteration. The trick is: do not jump into recursion, but use clear definitions to implement algorithm logic.

To deal with seemingly difficult problems, you can try to break the whole into parts, modify some simple solutions, and solve difficult problems.

## full code

```class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
// base case
if (m == 1) {
}
// Advance to the start of the reversal to trigger the base case
}

ListNode successor = null; // rear drive node

// Reverse the n nodes starting from head and return the new head node
ListNode reverseN(ListNode head, int n) {
if (n == 1) {
// record the n+1th node
}
// Take head.next as the starting point and need to reverse the first n - 1 nodes
ListNode last = reverseN(head.next, n - 1);