链表内指定区域反转

[题](链表内指定区间反转_牛客题霸_牛客网 (nowcoder.com))

1. 代码

   /**
    * struct ListNode {
    *  int val;
    *  struct ListNode *next;
    * };
    */
   
   #include <cstddef>
   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* temHead=new ListNode(0);//c++的创建方法，0是data域
           //创建虚拟头节点
           //操作头节点方便，比如如果反转第一个元素
            temHead->next=head;
           
           
            ListNode* pre=temHead;
            ListNode* cur=head;
           //两个指针用于操作来链表
           
            ListNode* tem=nullptr;
           //用于存放cur->next
           
           for (int i = 1; i < m; ++i) {
               pre=pre->next;
               cur=cur->next;
           }
           //使节点移动
           
           for (int i=0; i<n-m;++i) {
               tem=cur->next;
               cur->next=tem->next;
               //始终让cur->next指向的使next->xext;
               
               
               tem->next=pre->next;
               //让反转的指针，指向pre->next实现反转
               
               pre->next=tem;
               //再让pre指向tem保持连接
               
           }
           
           return temHead->next;
       }
   };

2. 提示

   

3. 理解

   • 先遍历到反转区域
   • 使用虚拟头节点

4. 问题

   • 为什么不用判断cur->next->next是不是越界？

     因为不会越界

     如果使用的区域刚好是整个链表

     那么当要反转最后一个节点的时候，也就是最后一次

     cur->next->next=nullptr