题解 | #链表内指定区间反转#

区间分为[...]->[prev]->[h]->[...]->[t]->[tail]->[...]
要反转的是h和t之间的节点（包括h和t）

// 反转区间[head, tail]
pair<ListNode*, ListNode*> reverseList(ListNode* head, ListNode* tail) {
  ListNode* p = nullptr;
  ListNode* q = head;
  ListNode* r = nullptr;
  ListNode* end = tail->next;
  while (q != end) {
    r = q->next;
    q->next = p;
    p = q;
    q = r;
  }
  return make_pair(tail, head);
}

ListNode* reverseBetween(ListNode* head, int m, int n) {
  if (head == nullptr || m == n) return head;
  auto dummy = new ListNode(-1);
  dummy->next = head;
  auto prev = dummy;
  for (int i = 1; i < m; ++i) {
    prev = prev->next;
  }
  auto t = prev->next;
  for (int i = m; i < n; ++i) {
    t = t->next;
  }
  auto h = prev->next;
  prev->next = nullptr;
  auto next = t->next;
  t->next = nullptr;
  auto pr = reverseList(h, t);
  prev->next = pr.first;
  pr.second->next = next;
  return dummy->next;
}

ListNode* CreateList(vector<int>& vec) {
  auto dummy = new ListNode(0);
  auto p = dummy;
  for (auto v : vec) {
    auto node = new ListNode(v);
    p->next = node;
    p = p->next;
  }
  return dummy->next;
}

int main() {
  vector<int> vec{ 1,2,3,4,5 };
  auto head = CreateList(vec);
  auto ans = reverseBetween(head, 2, 4);
  return 0;
}