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

非常原始的方法：遍历找到需要反转的部分链表，翻转后重新连接

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @param m int整型
 * @param n int整型
 * @return ListNode类
 */
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    // write code here
     
    if(!head){
        return head;
    }
     
    if(n==m){
        return head;
    }
     
    //找到需要反转的头
    int count_m=1;
    struct ListNode* org_head=head;
    if(m==1){ //如果m是1，反转前的部分链表头就是整个链表头
        org_head=head;
    }
    else{
        while(count_m<m){
               org_head=org_head->next;
                count_m++;
            }
    }
 
    //找到反转头前一个节点
    struct ListNode* org_head_pre=head;
    int count_m2=1;
    if(m==1){ //如果m是1，需要反转的部分链表头的前一个节点是NULL，其实如果m是1，是用不到部分链表头的前一个节点的
        org_head_pre=NULL;
    }else{
        while(count_m2<m-1){
                org_head_pre=org_head_pre->next;
                count_m2++;
            }
    }
         
    //找到反转的尾
    int count_n=1;
    struct ListNode* org_tail=head;
    while(count_n<n){
        org_tail=org_tail->next;
        count_n++;
    }
 
    //找到反转尾的下一个节点
    int count_n2=1;
    struct ListNode* org_tail_next=head;
    while(count_n2<=n){
        org_tail_next=org_tail_next->next;
        count_n2++;
    }
     
    //原地反转法将需要反转的部分链表反转
    struct ListNode* pre=org_tail_next;
    struct ListNode* cur=org_head;
    struct ListNode* next=cur->next;
    while(cur!=org_tail_next){
        cur->next=pre;
        pre=cur;
        cur=next;
        next=next->next;
    }
     
    //如果m不是1，要重新链接链表头和下一个节点，如果m是1，只需要把反转后的链表头返回
    if(m!=1){
        org_head_pre->next=pre; 
    }else{
        head=pre;
    }
     
    return head;
}