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

/**
 * 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 == n)
    {
        return head;
    }
    struct ListNode* first = head;
    struct ListNode* last = head;
    struct ListNode* first_front = head;
    struct ListNode* last_behind = head;
    int i = 1;
    while(first) //找头
    {
        if(i == m)
        {
            break;
        }
        i++;
        first_front = first;
        first = first->next;
    }
    last = first;
    while(last) //找尾
    {
        if(i == n)
        {
            last_behind = last->next;
            break;
        }
        i++;
        last = last->next;
    }
    struct ListNode* front = first;
    struct ListNode* behind = first;
    struct ListNode* final = first;
    while(front != last)
    {
        if(front == first)
        {
            behind = front->next;
            final = behind->next;
            if(last->next == NULL) //当n为最后一个结点时
            {
                front->next = NULL;
            }
            else 
            {
                front->next = last_behind;
            }
            behind->next = front;
        }
        else 
        {
            behind->next = front;
        }
        front = behind;
        behind = final;
        if(behind != NULL)
        {
            final = final->next;
        }
    }
    if(first == head) //当m为第一个结点时
    {
        head = last;
    }
    else 
    {
        first_front->next = last;
    }
    return head;
    
}