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

/**
 * 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* L = (struct ListNode*)malloc(sizeof(struct ListNode));
//L指向第一个结点
    L->next = head;
//创建cur，遍历每一个结点，从0开始，也就是虚拟头节点。
    struct ListNode* cur = L;
//寻找待翻转区间的头节点，指向翻转区间第一个结点的结点。
    int count = m;
    while (--count) {
        cur = cur->next;
    }

//创建一个新的虚拟头节点变量，保存待翻转区间的头节点
    struct ListNode* newhead = cur;

//创建一个新的node变量保存翻转区间的第一个结点的地址
    cur = cur->next;
    struct ListNode* temp = cur;

//创建一个新的node变量保存去遍历区间的第一个结点的地址
    struct ListNode* nextnode = NULL;

    count = n - m + 1;
    while (count--) {
        //记录下一个地址
        nextnode = cur->next;

//头插法
        cur->next = newhead->next;
        newhead->next = cur;

//更新到下一结点
        cur = nextnode;
    }

    //头插法以后区间第一个结点的地址已经被反转到区间最后一个地址，此时，要将他指向原来区间最后一个结点指向的地址

    //否则他会一直指向自己的地址。因此第一次头插法使得p指向p自己。
    temp->next = cur;
    return L->next;

}