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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
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* p=head;
        // 最多只有一个元素或者反转的位置为同一个
        if(p == nullptr || n == m){
            return p;
        }
        ListNode* q=p->next;
        //有两个元素
       if(q->next==nullptr){
         q->next=p;
         p->next=nullptr;
         return q;   
       }
       //三个元素以上
       int i=1;
       ListNode* t=q->next;
       ListNode* first=nullptr;
    //    ListNode* end=nullptr;
       while(i<n-1){
           if(i==m-1){
              first = p;
           }
              ///反转链表
            if(i>=m)
                 q->next=p; 
             p=q;
             q=t;
             t=t->next;
             i++;
       }
          q->next=p;
          if(first==nullptr){
              head->next=t;
              head=q;
          }else{
             first->next->next=t;
              first->next=q;
          }    
        return head;
    }
};

一般链表题的话，可以先解决一般的情况，最后再考虑一些特殊情况。

一般的思路就是，我们要获取到开始进行反转序号的前一个结点（这里我命名为first），因为这个节点会帮助我们最后链表的拼接。然后就是在给定的区间将链表反转。反转完成之后，将我们获取到的first的next指向反转区间的下一个元素，再将first指向反转区间的最后一个元素。

特殊情况就是，给定的反转区间的开始序号是1，那么就无法获取到这个的前一个节点，并且序号为1的话也就代表当前位置就是头节点，那么这种情况到最后链表的拼接就要做一些特殊处理，若first是为空的，那么就将head的next指向反转区间的下一个元素，再将head变成反转区间的最后一个元素。