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

/**

• struct ListNode {
• int val;
• struct ListNode *next;
• }; */

class Solution { public: /** * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 / ListNode reverseBetween(ListNode* head, int m, int n) { // write code here ListNode* pHead=head;//保证在链表头部的时候不会是空指针 ListNode* pend;//要反转的右边的那个元素的指针

    ListNode* nex;
    ListNode* pHeadp = new ListNode(0);//如果一开始就指向的是头节点，那么当出现{1，2，3，4，5}，1，5这个例子的时候，就会导致，最后的一个链表是一个
                          //无线循环链表，所以算法还是得要先修改
    ListNode* pende;
    ListNode* tem = head;
    //考虑到有两种情况，一个是当m==1的时候，一个是当m!=1的时候
    ListNode*s = new ListNode(1);//注意这里的新建立的节点必须要给定一个值，不然在调用->next的时候会导致无限循环
    //接下来是根据m,n的值来建立对应的四个指针的值
    for(int  i =0;i<m-1;++i)
    {
       pHead = tem->next;
        //这里要用到的是head=head->next
        //不然总是会出现
       tem = tem->next;//注意这里不能是这么赋值，要先把原始的值赋给指针，再将指针递增。
    }//找到要反转左边元素的指针
    tem = head;//这里需要重置以下
    for(int  i =0;i<m-1;++i)
    {
       pHeadp = tem;
         tem= tem->next;
    }//找到左边反转元素的前面一个指针
    tem = head;//同理
    for(int i =0;i<n-1;++i)
    {
      pend = tem->next;
          tem= tem->next;
    }//找到反转的右边的元素的指针
    tem = head;//同理
    for(int i =0;i<n;++i)
    {
       pende = tem->next;
          tem= tem->next;
    }//找到有边元素后面对应的指针
     ListNode * pre = pende;//记录连接到指定区域元素的后一位
     
    while(pHead!=pende)
    {
        nex = pHead->next;
        pHead->next = pre;
        pre = pHead;
        pHead = nex;
                  
    }//进行反转元素的算法，方法是根据前面的第一道题目的反转直接摘抄的 
    pHeadp->next = pre;//记录链接到指定区域元素的最开始的那位
    if(m==1)   //这里当最前面的元素需要考虑的时候，需要返回一个指针
    {
      s=pre;
    }
    else //当最前面的元素不需要反转的时候，反转返回的指针就只要返回原来的指针，只不过后面					//不过是的地址发生了变换。
    {
        s=head;
    }
    return s;//这里需要返回以下
    
    
}

};