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

大致思路：

①找出 m - n 段的起始地址

②对被选中部分的端点做值互换（地址不变）

③将（m+1）-（n-1）段用头插法拼接在n+段的开头

④将头插法生成的段 (m+1)+ 拼接在1-m段后面

/**
 * 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 ) {
    struct ListNode *p1,*p2;
    struct ListNode *p = head;
    int idx = 0;

    //分别找第m个节点和第n个节点的地址
    while(p!=NULL){
        ++idx;
        if(idx == m){
            p1 = p;
        }
        if(idx == n){
            p2 = p;
            break;
        }
        p = p->next;
    }

    
    if(p1 == p2)return head; //p1 == p2 , 无需逆置
    else { 
        //被逆置的部分长度至少为2

        //交换端点值
        int temp = p1->val;
        p1->val = p2->val;
        p2->val = temp;

        //掐掉端点，对p1-p2剩余部分遍历，头插法依次拼接至p4打头的新链表
        struct ListNode *p3 = p1->next;
        struct ListNode *p4 = p2;
        while(p3!=p2){
            struct ListNode *r = p3->next;
            p3->next = p4;
            p4 = p3;
            p3 = r;
        }
        
        //将头插法生成的新链表拼接至p1后面
        p1->next = p4;
        return head;
    }
    // write code here
}