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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param m int整型 
 * @param n int整型 
 * @return ListNode类
 */
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    // write code here
    struct ListNode* vhead = (struct ListNode*)malloc(sizeof(struct ListNode));//虚拟头节点
    vhead->next = head;
    struct ListNode* pHead = vhead;
    struct ListNode* cur = NULL;
    struct ListNode* end = vhead;
    struct ListNode* pre = NULL;
    struct ListNode* next = NULL;
    
    while(--m)// 从head开始计数，所以要先-1
    {
        pHead = pHead->next;//让pHead停在m节点的前一节点上
    }
    cur = pHead->next;//cur指向m节点
    while(n--)// 从head开始计数，刚好停在n节点
    {
        end = end->next;//让end停在n节点
    }
    pre = end->next;//记录n节点的后一个节点
    while(cur != end)//开始反转
    {
        next = cur->next;
        cur->next =pre;//第一次循环先让m节点指向n节点的后一个节点
        pre = cur;
        cur = next;//移动到下一个节点
    }
    cur->next = pre;//n节点指向前一个反转的节点
    pHead->next = cur;//让反转前的m节点的前一节点指向n节点
    return vhead->next;
}
//参考自牛客559548009号大佬的思路