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 *reverse(ListNode *head) {
14
    ListNode *prev = NULL;
15
    while (head != NULL) {
16
      ListNode *temp = head->next;
17
      head->next = prev;
18
      prev = head;
19
      head = temp;
20
    }
21
    return prev;
22
  }
23

24
  ListNode *reverseN(ListNode *head, int right) {
25
    ListNode *temp = head;
26
    while (right != 1) temp = temp->next, right--;
27

28
    ListNode *temp2 = temp->next;
29
    temp->next = NULL;
30

31
    ListNode *ans = reverse(head);
32
    head->next = temp2;
33
    return ans;
34
  }
35

36
  ListNode *reverseBetween(ListNode *head, int left, int right) {
37
    if (left == right) return head;
38

39
    if (left == 1) {
40
      return reverseN(head, right);
41
    } else {
42
      ListNode *temp = head;
43
      right--;
44
      while (left != 2) {
45
        temp = temp->next;
46
        left--;
47
        right--;
48
      }
49
      ListNode *temp2 = reverseN(temp->next, right);
50
      temp->next = temp2;
51
      return head;
52
    }
53

54
    return NULL;
55
  }
56
};