【链表】206. Reverse Linked List; 92. Reverse Linked List II

问题：

206.链表反转。

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

92.指定区间链表反转。

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

解法：Recursion（递归）

206.

1.递归获得2～6，反转后的结果。

2.将2->next指针，指向1:

由于原来1->next=2，因此 (1->next)->next = 1

3.将1->next指向NULL

BASE：

只有一个节点 or 0个节点，return head

代码参考：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode() : val(0), next(nullptr) {}
 7  *     ListNode(int x) : val(x), next(nullptr) {}
 8  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 9  * };
10  */
11 class Solution {
12 public:
13     //1->reverseList(2<-3<-4<-5)
14     ListNode* reverseList(ListNode* head) {
15         //base
16         if(!head || !head->next) return head;
17         //recursion
18         ListNode* newhead = reverseList(head->next);
19         //OPT
20         head->next->next = head;
21         head->next = nullptr;
22         return newhead;
23     }
24 };

92.

先解决，如何反转前n个节点。

reverseN(ListNode* head, int n)

相较于206，多了第n个节点之后的，不需要反转的节点successor

因此，比206多出的处理：

★BASE：
- 记录successor节点，n==1的时候，只剩一个节点
- successor = head->next
recursion后的　★OPT：
- head->next=successor

即，代码为：

 1     ListNode* reverseN(ListNode* head, int n) {
 2         //base
 3         if(n==1) {
 4             successor = head->next;//★BASE
 5             return head;
 6         }
 7         //recursion
 8         ListNode* newhead = reverseN(head->next, n-1);
 9         //OPT
10         head->next->next = head;
11         head->next = successor;//★OPT
12         return newhead;
13     }

接下来，解决从第m个开始，

递归到m==1，则变成上面的问题，直接调用reverseN即可。

其他情况，依次递归，不用更改任何指针。

⚠️ 注意：从第0个移动到第m个时的递归中，

返回值：当前的新头。所以，head->next=上次递归的结果。

代码为：

1     ListNode* reverseBetween(ListNode* head, int m, int n) {
2         if(!head || !head->next) return head;
3         if(m==1) return reverseN(head, n);
4         head->next = reverseBetween(head->next, m-1, n-1);
5         return head;
6     }

代码参考：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode() : val(0), next(nullptr) {}
 7  *     ListNode(int x) : val(x), next(nullptr) {}
 8  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 9  * };
10  */
11 class Solution {
12 public:
13     ListNode* successor;
14     ListNode* reverseBetween(ListNode* head, int m, int n) {
15         if(!head || !head->next) return head;
16         if(m==1) return reverseN(head, n);
17         head->next = reverseBetween(head->next, m-1, n-1);
18         return head;
19     }
20     ListNode* reverseN(ListNode* head, int n) {
21         //base
22         if(n==1) {
23             successor = head->next;
24             return head;
25         }
26         //recursion
27         ListNode* newhead = reverseN(head->next, n-1);
28         //OPT
29         head->next->next = head;
30         head->next = successor;
31         return newhead;
32     }
33 };