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

方法

1. 找到反转区间的首尾地址[pos_m, pos_n]，并记录左边界的前一个位置pre_m，右边界的后一个位置next_n
2. 单独反转区间,返回反转后的链表首地址pp（反转函数内部以及将反转后的链表尾部指向next_n了）
3. 进行拼接：pre_m-<next = pp; (pp尾部的拼接在2中已经做好了)
4. 需要注意的是当pos_m就是链表尾部的时候，直接返回pp即可，不用拼接前面（也拼接不了，此时pre_m为nullptr）

 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseList(ListNode *low, ListNode *high, ListNode *tail) {
        ListNode *pre = tail;
        ListNode * cur = low;
        while (cur != high) {
            ListNode *tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        ListNode *pre_m = nullptr;
        ListNode *pos_m = head;
        ListNode *pos_n = head;
        ListNode *next_n = nullptr;
        while (pos_m && m > 1) {
            pre_m = pos_m;
            pos_m = pos_m->next;
            m--;
        }
        while (pos_n && n > 1) {
            pos_n = pos_n->next;
            n--;
        }
        next_n = pos_n->next;
        ListNode *pp = reverseList(pos_m, pos_n->next, next_n);
        if (pre_m == nullptr){
            return pp;
        }else {
            pre_m->next = pp;
        }
        return head;
    }
};