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

链表题，多定义几个指针变量有助于保持头脑清醒

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    
    pair<ListNode*,ListNode*> reverseLocal(ListNode* front,ListNode* tail){
        ListNode* pre = nullptr;
        ListNode* cur = front;
        while(cur!=tail){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        cur->next = pre;
        return{cur,front};
    }
    
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        /*
            1.定位到pre,front,tail和succ
            2.局部反转函数
            3.断开连接，局部反转
            4.拼接回原链表
        */
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* cur = dummy;
        ListNode* pre;
        ListNode* front;
        ListNode* tail;
        ListNode* succ;
        
        for(int i = 0;i <=n ; i++ ){
            if( i == m - 1 ) // step into pre
                pre = cur;
            if( i == m )    // step into front
                front = cur;
            if( i == n ){
                tail = cur;
                succ = cur->next;
            }
            cur = cur-> next;            
        }
        
        // disconnect the origin linkedlist
        pre->next = nullptr;
        tail->next = nullptr;
        
        // reverseLocal
        auto tmp = reverseLocal(front,tail);
        // update front and tail
        front = tmp.first;
        tail = tmp.second;
        
        // concact the origin linkedlist
        pre->next = front;
        tail->next = succ;
        
        return dummy->next;
        
    }
};