leetcode92 反转链表II

思路：

这里记录一种递归实现的方法，参考了https://zhuanlan.zhihu.com/p/86745433。

实现：

 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 {
13 public:
14     ListNode* tail = NULL;
15     ListNode* reverseN(ListNode* head, int N)
16     {
17         if (N == 1) { tail = head->next; return head; }
18         ListNode* res = reverseN(head->next, N - 1);
19         head->next->next = head;
20         head->next = tail;
21         return res; 
22     }
23     ListNode* reverseBetween(ListNode* head, int left, int right)
24     {
25         if (left == 1) return reverseN(head, right);
26         head->next = reverseBetween(head->next, left - 1, right - 1);
27         return head;
28     }
29 };