# 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

reprint labuladong's solution

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) { if (head.next == null) return head; ListNode last = reverse(head.next); head.next.next = head; head.next = null; 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) ListNode reverseN(ListNode head, int n)

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 successor = head.next; return head; } // Take head.next as the starting point and need to reverse the first n - 1 nodes ListNode last = reverseN(head.next, n - 1); head.next.next = head; // Connect the inverted head node to the next node head.next = successor; 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 return reverseN(head, n); } // ... }

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) { return reverseN(head, n); } // Advance to the start of the reversal to trigger the base case head.next = reverseBetween(head.next, m - 1, n - 1); return head; }

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) { return reverseN(head, n); } // Advance to the start of the reversal to trigger the base case head.next = reverseBetween(head.next, m - 1, n - 1); return head; } 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 successor = head.next; return head; } // Take head.next as the starting point and need to reverse the first n - 1 nodes ListNode last = reverseN(head.next, n - 1); head.next.next = head; // Connect the inverted head node to the next node head.next = successor; return last; } }

Execution time: 0 ms, beat 100.00% of users in all Java commits

Memory consumption: 37.3 MB, beating 8.70% of users across all Java commits