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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @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(m==1){
        struct ListNode* s = NULL;  //用于辅助链表逆置
        struct ListNode* p = head;  //用于遍历链表和辅助链表逆置
        struct ListNode* pend = head;

        head = NULL;
        for(int i=1;i<n+1;i++){  //循环结束后，p指向n位置的下一个，且1~n位置的结点都已经逆置
            s = p;
            p = p->next;
            s->next = head;
            head = s;
        }

        pend = head;  //pend的值需要更新，因为原来head的值经过逆置后已经被改变
        while(pend->next!=NULL){  //找到逆置后链表的最后一个结点，即n位置的结点
            pend = pend->next;
        }
        pend->next = p; //将逆置好的链表和之前n位置后被断开的结点相连

        return head;  //返回整个链表
    }else{
        int i = 0,j = 0;
        struct ListNode* pm=head;
        struct ListNode* pn=head;
        struct ListNode* p = NULL; //用来遍历m~n
        struct ListNode* pend = head; //用来找尾巴


        struct ListNode* s=NULL;

        for(i=1;i<m-1;i++){ //把m位置的前一个结点当头结点，pm指向这个头结点
            pm = pm->next;
        }
        p = pm->next; //p指向pm的下一个节点，用来遍历和逆置

        for(j=1;j<n+1;j++){  //把n位置的后一个当链表的结尾，相当于末尾的NULL
            pn = pn->next;
        }

        pm->next = NULL;
        while(p!=pn){  //循环结束后p指向的是n位置后的一个结点
            s = p;
            p = p->next;
            s->next = pm->next;
            pm->next = s;
        }

        while(pend->next!=NULL)
        {
            pend = pend->next;
        }
        pend->next=p;

        return head;
    }
}

写的比较复杂，但是好理解，还可以优化的更简洁