链表内指定区间反转

引入哑节点，先反转子链表，再连接：

//
// Created by jt on 2020/9/24.
//
class Solution {
public:
    /**
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        ListNode *pre, *post;  // 分别保存子链的前一个节点和子链的后一个节点
        ListNode *begin, *end; // 分别保存子链的第一个节点和子链的最后一个节点
        ListNode dummy(0); dummy.next = head;
        ListNode *p = &dummy;
        int cnt = 0;
        while (cnt <= n) {
            if (cnt+1 == m) { pre = p; begin = p->next; }
            if (cnt == n) { end = p; post = p->next; }
            ++cnt; p = p->next;
        }
        // 断链并反转
        ListNode *q = begin;  // 保存反序后的头
        p = begin->next;
        while (p != post) {
            ListNode *tmp = p->next;
            p->next = q;
            q = p; p = tmp;
        }
        // 重新合链
        pre->next = end;
        begin->next = post;
        return dummy.next;
    }
};