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

分享交流思路在代码中

/**
 * 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)
{
    if (m==n) {//不用移动
    return head;
    }
    // write code here
    struct ListNode *pre = NULL; // 记录弟m的前一个结点
    struct ListNode *end = head; // 记录弟n的后一个结点
    struct ListNode *p1 = head;//弟m个结点
    struct ListNode *p2;
    struct ListNode *p3;
    int i = 1;
    while (p1 && i < m)//找到弟m个结点
    {
        /* code */
        pre = p1;
        p1 = p1->next;
        i++;
    }
    // printf("%d\n",p1->val);
    i = 0;
    while (end && i < n)//找到n的下一个结点
    {
        end = end->next;
        i++;
    }
    //  printf("%d\n",end->val);
    //进行区间翻转
    struct ListNode *begin=p1;
    p2 = p1->next;
    p3 = p2;
    i = m;
    while (p2 && i < n)
    {
        p3 = p3->next;
        p2->next = p1;
        p1 = p2;
        p2 = p3;
        i++;
    }
    begin->next=end;//把原本第一个结点接到弟n个结点之后
    //我特判了一下是否逆转了头结点，如果不特判会出现内存错误，暂时没有改进方法
    if (pre!=NULL) {
        pre->next=p1;//反转后的弟n个结点连接弟m的前一个
    }else {
        head=p1;
    }
    return head;
}