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

//反转链表，把反转之后的链表末节点连接到原本链表断开的地方
struct ListNode* remake( struct ListNode* head,struct ListNode* tail )
{
    struct ListNode* pre = tail;
    
    struct ListNode* now = head;
    
    struct ListNode* nex = head->next;
    
    
    while( now )
    {
        now->next = pre;
        pre = now;
        now = nex;
        if( nex )  nex = nex->next;
    }
    
    return pre;
}


struct ListNode* reverseBetween(struct ListNode* head, int m, int n )
{
    if( m == n || head == NULL ) return head;
    
    
    struct ListNode* dummy = ( struct ListNode* )malloc( sizeof(struct ListNode) );
    
    dummy->next = head;
    
    struct ListNode*  p = dummy;
    
    //定义四个指针 分别指向反转区间 和 原本链表  的交界区的四个节点
    struct ListNode* pre = NULL;
    
    struct ListNode* cur = NULL;
    
    struct ListNode* left_head = NULL;
    
    struct ListNode* right_head = NULL;
        
    
    for( int i = 0;i < m-1;i++ )
    {
        p = p->next;
    }
    
    pre = p;        //定位反转区间前一个节点
    
    left_head = p->next;        //定位反转区间的第一个节点
    
    
    for( int i = 0;i < n-m+1;i++ )
    {
        p = p->next;
    }    
    
    right_head = p;              //定位反转区间的最后一个节点
    
    
    cur = right_head->next;      //定位反转区间最后一个节点的下一个节点
    
    
    //定位所有有用的节点之后就可以断开原本链表和反转区间的连接部分
    
    pre->next = NULL;
    
    right_head->next = NULL;
    
    
    pre->next = remake( left_head,cur );
    
    return dummy->next;
    
}