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

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

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* res = new ListNode(0);
        res->next = head;
        ListNode *pre = res;
        ListNode *curr = head;
        int cnt = 1;
        //定位到反转区间的第一个结点
        while(cnt <m)
        {
            pre =curr;
            curr = curr->next;
            cnt++;
        }
        //结束循环以后 pre指向结点m的前一个结点 curr指向结点m
        //待翻转区间为结点m到结点n,需要进行n-m次头插法（i不能包含n，否则就是n-m+1次）
        for(int i = m;i<n;++i)
        {
            //头插法翻转序列区间
            //每次将curr的下一结点以头插法的方法插入到pre结点和pre->next结点中间，实现逆序
            //curr一直没变，指向的是m结点；pre也一直没变，指向的是m-1结点
            //curr一直后移直到区间尾，中间的数从小到大依次插入到了pre结点和pre->next结点中间，实现反转
            ListNode *temp = curr->next;//记录curr的下一结点，也就是接下来要插入到前面pre和pre->next之间的结点
            curr ->next = temp ->next;//curr的next指向temp的下一结点，以实现将结点m后移
            //使用头插法在pre和pre->next之间插入temp结点
            temp ->next = pre->next;
            pre ->next = temp;
            
        }
        return res->next;
        
    }
};