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

/**
 * 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
        //遍历两遍，时间复杂度为2*n
        //空间复杂度为o(1),不能用stack存
        ListNode* addNode = new ListNode(0); //额外加在前面，防止m=1
        addNode->next = head;
        ListNode* startNode = head;//m前一个
        ListNode* startNodeNext;//m个
        ListNode* endNode = head;//第n个
        if(m==1){
            startNode = addNode;
        }else{
            for(int i=1;i<m-1;i++){//从第一个到 m-2+1 = m-1个, m大于0，注意要有特殊情况如果m=1怎么办?加addNode
                startNode = startNode->next;
            }
        }
        startNodeNext = startNode->next;
        endNode = startNode;
        for(int i=m-1;i<n;i++){//从第m-1个到 n-m+1+m-1 = n个
            endNode = endNode->next;
        }
        ListNode* tmp;
        for(int i=m;i<n;i++){//n-m次,要特判，注意next->next要的长度
            tmp = startNodeNext->next;
            startNodeNext->next = endNode->next;
            endNode->next = startNodeNext;
            startNodeNext = tmp;
        }
        startNode->next = endNode;
        return addNode->next;
    }
};