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

struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    int k  = 1;
    if(m == n)
        return head;  //只反转单个结点相当于不反转
    struct ListNode* phead = (struct ListNode*)malloc(sizeof(struct ListNode));
    //加一个虚拟头结点更方便操作
    phead->next = head;  //指向第一个结点
    struct ListNode *pre = phead, *p = head;  //用pre找到前驱
    struct ListNode *q, *r;
    while(k < m){
        pre = pre->next;  //直到开始反转的前一个结点
        k++;
    }   
    p = pre->next;   //开始反转的结点
    r = pre->next;  //翻转后的接口
    pre->next = NULL;   //拆链后前链的末尾要置空
    struct ListNode * L = NULL;   //为反转链表加一个头指针
    while(k <= n ){  //开始反转
        q = p->next;
        p->next = L;
        L = p;
        p = q;
        k++;
    }
    if(p == NULL)  //一直反转到原链表表尾的情况
       pre->next = L;   //只需要链接前面接口
    else{
        pre->next = L;    //链接前面接口
        r->next = p;    //链接后面接口
    }
    return phead->next;  //无论从哪里开始反转，最后第一个结点都是虚头结点的下一个结点
}

struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    if( head == NULL || m == n)
        return head;  
    struct ListNode *xuhead = malloc(sizeof(struct ListNode));  //虚头结点
    xuhead->next = head;  //虚头结点的指针域指向第一个结点
    struct ListNode * p = xuhead;  //p指针用来找到第一个反转结点的前驱，初始指空
    for(int i = 0; i<m-1; i++)  //m=1时，p不动；m=1时，p走一步
        p = p->next;  //p停在待反转的结点的前驱，且一直不变
    struct ListNode* r = p->next;  //r指向第一个反转结点
    struct ListNode* tmp;  //用来跟踪后继，以防掉链
    for(int i = 0; i< n-m; i++){  //循环n-m次
        tmp = r->next;  //暂存后继
        r->next = tmp->next;  
        tmp->next = p->next;
        p->next = tmp;
    }
    return xuhead->next;
}