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

struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) 
{
    struct ListNode *p = head;//遍历指针
    struct ListNode *pre = NULL;//当m不等于1时用来指向m位置前的那一个结点
    struct ListNode *pm = NULL;//用来保存m位置的结点
    struct ListNode *pn =NULL;//用来保存n位置的结点
    int i = 1;//用来指示何时找到m,n位置结点
    while(1)
    {
        if(i == m)
        {
            if(m>1)
            {
                pre->next = NULL;
            }
            pm = p;
        }
        if(i == n)
        {
            pn = p; 
            p = p->next;
            pn->next = NULL;
            break;
        }
        if(i<m)
        {
            pre = p;
            p = p->next;
        }
        else
        {
            p = p->next;
        }
        i++;
    }
    struct ListNode *p1 = NULL;
    struct ListNode *p2 = NULL;
    pn = pm;//因为自逆后第一个结点会成为最后一个结点故直接指向
    p1 = pm;//自逆遍历指针
    while(p1)
    {
        if(p1 == pm)
        {
            p1 = p1->next;
            pm->next = NULL;
        }
        else
        {
            p2 = p1;
            p1 = p1->next;
            p2->next = NULL;
            p2->next = pm;
            pm = p2;
        }
    }
    /*当m等于1时只需要接上原来链表中n位置后的结点*/
    if(m==1)
    {
        pn->next = p;
        return pm;
    }
    else
    {
        pre->next = pm;
        pn->next = p;
        return head;
    }                                         // write code here
}