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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param m int整型 
 * @param n int整型 
 * @return ListNode类
 */

 typedef struct ListNode* Listlink;

 Listlink reverseList(Listlink L);
 Listlink reverse(Listlink pre,Listlink cru);
 int NumList(Listlink L);

struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    // write code here
    if(m==1&&n==1)
        return head;
    Listlink start,end;     //start与end节点均保持在不翻转的链表中
    Listlink h,e;           //h,e分别为反转部分的头尾

    int num=NumList(head);

    if(m==1&&n==num){
        head=reverseList(head);
        return head;
    }

    int i;
    start=head;
    e=head;

    //首先，找到链表的m-1个元素
    for(i=1;i<m-1;i++){
        start=start->next;
    }
    //找到链表的第n个元素
    for(i=1;i<n;i++){
        e=e->next;
    }

    //标记反转部分的起点、终点
    //将不反转的部分分离出去
    end=e->next;
    e->next=NULL;
    //处理开始部分的特殊情况
    if(m==1)
        h=start;
    else{
        h=start->next;
        start->next=end;
    }
        
    

    e=reverseList(h);   //反转后，反转部分的最后一个节点成为反转部分的头结点

    if(m==1){
        head=e;
        h->next=end;
        return head;
    }
    start->next=e;
    h->next=end;
    return head;
}
Listlink reverseList(Listlink L){
    if(L==NULL||L->next==NULL)
        return L;
    
    L=reverse(NULL,L);
    return L;

}

Listlink reverse(Listlink pre,Listlink cru){
    if(cru==NULL)
        return pre;

    Listlink temp;
    temp=cru->next;
    cru->next=pre;
    return reverse(cru,temp);
}

int NumList(Listlink L){
    int cot=0;
    Listlink p=L;
    if(L==NULL)
        return cot;
    while(p){
        p=p->next;
        cot++;
    }
    return cot;
}