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