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

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 
        //快慢指针解决，时间复杂度O(N),空间复杂度为O(1)
        int length=n-m;
        if(length<=0)
            return head;
        ListNode* pHead=new ListNode(0);
        pHead->next=head;
        ListNode* first=pHead,*second=pHead;
        for(int i=0;i<n&&first->next!=NULL;i++)
        {
            first=first->next;
            if(length<i)
                second=second->next;
        }
        ListNode* firstNext=first->next;
        ListNode* secondNext=second->next;
        ListNode* Next=secondNext->next;
        secondNext->next=firstNext;
        while(Next!=firstNext)
        {
            ListNode* tmp=Next->next;
            second->next=Next;
            second->next->next=secondNext;
            secondNext=Next;
            Next=tmp;
        }
        return pHead->next;
    }
};