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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @param m int整型
 * @param n int整型
 * @return ListNode类
 */
#include <stdlib.h>
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    // write code here
    //定义一个哨兵位，防止从第一个开始反转
    struct ListNode*  first=malloc(sizeof(struct ListNode));
    first->next=head;
    struct ListNode* newhead = first;
    struct ListNode* mprev;
    struct ListNode* mhead;
    struct ListNode* mtail;
    struct ListNode* cur;
    /* 
        newhead用来存放m节点前一个
        mtail用来存放m节点，即反转后的尾节点
        mprev用来存储反转后的头节点
    */
    int i=m;
    while(--i)
        newhead=newhead->next;  
    mtail=cur=mhead=newhead->next;
    //反转m节点到n节点，mhead和cur用来反转链表，同时反转结束后mhead指向n节点的后一个
    i=n-m+1;
    while(i--)
    {   
       cur=mhead;  
       mhead=mhead->next;
       cur->next=mprev;
       mprev=cur;
    }
    newhead->next=mprev;
    mtail->next=mhead;
    cur=first->next;
    free(first);
    return cur;
}