1. Description of the problem
English description
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:
Example 2:
Constraints:
The number of nodes in the list is n.
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= nFollow up: Could you do it in one pass?
Product description
Give you the head pointer to the singly linked list head and two integers left and right, where left <= right. Reverse the list node from position left to position right to return the reversed list.
Example 1:
Example 2:
Tip:
The number of nodes in the linked list is N 1 <= n <= 500-500 <= node. val <= 500 1 <= left <= right <= n
Source: LeetCode link: leetcode-cn.com/problems/re… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
Second, the idea of solving the problem
Consider a question: how to reverse the first N nodes of a linked list
- One method is to use the head interpolation method (iteration), record the number of nodes inserted into the head, and stop when N is reached. You also need to record two locations: the head node and the next node that needs to be inserted after the head node. (Since the operation is carried out in the original linked list, extra care should be taken in the stripping and reinserting of nodes and the principle of unique directivity of the whole linked list must be ensured.)
- One is the recursive method, which only needs to ensure that the number of inversion nodes is N.
As you can see from the above, the recursive approach is much easier to implement and requires little to add, although recursive implementations tend to be less memory consuming. (Constantly pushing variables onto the stack)
Now that you have a way to reverse the first N nodes, all you need to do is locate the head node and call the algorithm that reverses the first N nodes.
Since it is possible to reverse the linked list from the head node, you need to add a virtual head node.
When do you need to add a virtual head node?
A simple trick is to add virtual head nodes to simplify the algorithm when the head node may change, ensuring that there is always a stable start, thus avoiding all possible boundary problems. For example, insert, delete and so on in the possible header.
Three, AC code
Here only the concrete code implementation of recursive algorithm is given.
C++
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* ReverseN(ListNode* head, int n) { if(n == 0 || n == 1) return head; ListNode* tail = head->next, * h = ReverseN(head->next, n - 1); head->next = tail->next; tail->next = head; return h; } ListNode* reverseBetween(ListNode* head, int left, int right) { int cnt = right - left + 1; ListNode* h = new ListNode, * tem = h; h->next = head; while(--left) tem = tem->next; tem->next = ReverseN(tem->next, cnt); return h->next; }};Copy the codeJava
/** * 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 reverseN(ListNode head, int n) { if(n == 0 || n == 1) return head; ListNode tail = head.next; ListNode h = reverseN(head.next, n - 1); head.next = tail.next; tail.next = head; return h; } public ListNode reverseBetween(ListNode head, int left, int right) { int cnt = right - left + 1; ListNode h = new ListNode(); h.next = head; ListNode tem = h; while(--left > 0) tem = tem.next; tem.next = reverseN(tem.next, cnt); return h.next; }}Copy the codeFourth, the problem solving process
The first,
It’s easy to solve once you know the algorithm. It’s in
