/**
 * 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* H=new ListNode(0);
        H->next=head;
        ListNode *p=head,*p_pre=NULL,*q_last=NULL,*q,*pp=head,*pp_pre=H;//pp是遍指针
        for(int i=1;pp!=NULL;pp=pp->next,i++)
        {
            if(i==m)
            {
                p=pp;
                p_pre=pp_pre;
            }
            if(i==n) 
            {
                q=pp;
                q_last=pp->next;
            }
            pp_pre=pp;
        }
        //反转p到q
        if(p==q) return head;
        ListNode* t1=NULL,*t2=p;
      
        while(t2!=q_last)
        {
            ListNode* t3=t2->next;
            t2->next=t1;
            if(t2!=q_last) t1=t2;
            t2=t3;
        }
        p_pre->next=q;
        p->next=q_last;
        return H->next;
       // return head;
    }
};