反转链表 II

 1ListNode* reverse(ListNode* prev, ListNode* curr, ListNode* last)
 2{
 3    if(curr == last)
 4    {
 5        return prev;
 6    }
 7    ListNode* temp = curr->next;
 8    curr->next = prev;
 9    return reverse(curr, temp, last);
10}
11ListNode* reverseBetween(ListNode* head, int left, int right)
12{
13    ListNode* dummy = new ListNode(0);
14    dummy->next = head;
15    ListNode* pre = dummy;
16
17    // 找到 pre（left 的前一个节点）
18    for(int i = 1; i < left; i++)
19    {
20        pre = pre->next;
21    }
22    // 通过 pre 可以定位到 left
23    ListNode* left_node = pre->next;
24
25    // 找到 right 的下一个节点
26    ListNode* last = left_node;
27    for(int i = left; i <= right; i++)
28    {
29        last = last->next;
30    }
31
32    // 将【left，right】区间翻转
33    // 这里的 new_head 就是之前的 right
34    ListNode* new_head = reverse(nullptr, left_node, last);
35    pre->next = new_head;
36    left_node->next = last;
37
38    return dummy->next;
39}