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

/**
 * 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* Cur = head;
    struct ListNode* Prev = NULL;
    struct ListNode* temp1 = NULL;
    struct ListNode* temp2 = NULL;
    struct ListNode* Next = head->next;

    // 特殊情况处理
    if (m==n) {
        return head;
    }

    // 找到开始反转的节点，并记录开始反转的节点和前一个节点，分别是temp1，temp2
    for(int i = 0 ; i < m; i++)
    {
        temp2 = Prev;
        Prev = Cur;
        Cur = Next;
        Next = Next->next;
        temp1 = Prev;
    }
    // temp1 = Prev;
    // printf("%d",temp1->val);
    // printf("%d",temp2->val);

    // 对需要反转的区域进行反转
    for(int i = m ; i < n ; i++)
    {
        Cur->next = Prev;
        Prev = Cur;
        Cur = Next;
        if(Next != NULL)
        {
            Next = Next->next;
        }   
    }
    //printf("%d",Prev->val);

    // 进行反转区域的拼接
    temp1->next = Cur; 
    if(m == 1)  // 特殊情况处理
    {
        return Prev;
    }
    temp2->next = Prev;
    return head;
}






















// struct ListNode* reverseBetween(struct ListNode* head, int m, int n ){
//          //加个表头
//         struct ListNode* res = (struct ListNode*)malloc(sizeof(struct ListNode));
//         res->val = -1;
//         res->next = head;
//         //前序节点
//         struct ListNode* pre = res;
//         //当前节点
//         struct ListNode* cur = head;

//         struct ListNode* temp;
//         //找到m
//         for(int i = 1; i < m; i++){
//             pre = cur;
//             cur = cur->next;
//         }
//         //从m反转到n
//         for(int i = m; i < n; i++){
//             temp = cur->next;
//             cur->next = temp->next;
//             temp->next = pre->next;
//             pre->next = temp;
//         }
//         //返回去掉表头
//         return res->next;
//     }