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

/**
 * 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 ) {
    //思路
    //创建一个头结点，找到并指向结点m，把原链表从m结点处断开，m结点就作为了反序链表的第一个结点，将该结点后面的n-m个结点，全部依次前移；
    struct ListNode HeadNode = { NULL };
    struct ListNode *pReverseHead = NULL;
    struct ListNode *pMove = NULL;
    struct ListNode *pTemp = NULL;
    struct ListNode *pHeadPrevious = head;
    int i = 1;

    if (head == NULL) {
        return NULL;
    }

    //找到结点m
    pReverseHead = head;
    while (i < m) {
        pHeadPrevious = pReverseHead;
        pReverseHead = pReverseHead->next;
        i++;
    }
    HeadNode.next = pReverseHead; // 记录要反序的第一个结点
    pMove = pReverseHead->next; // 从第一个结点的下一个结点开始移动
    i = 0; //记录处理的结点个数，实现终止条件

    while ((i < (n - m)) && (pMove != NULL)) {
        pTemp = pMove; // 记录要被移动的成员
        pReverseHead->next = pTemp->next; //断链
        // 插入到头结点的后面，成为新的第一结点
        pTemp->next = HeadNode.next;
        HeadNode.next = pTemp;

        pMove = pReverseHead->next; // 继续处理下一个结点
        i++;
    }

    // 如果m为1，本身就是第一个结点，直接返回反序链表即可
    if (m == 1) {
        return HeadNode.next;
    }
    // 此方法相当于把原链表从m结点处断开了，如果实际移动了，需要将原链表与反序链表进行连接
    if (i > 0) {
        pHeadPrevious->next = HeadNode.next;
    }

    return head;
}