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

/**
 * 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*res=head;
        if(head==NULL||head->next==NULL)
            return head;
        //首先找到四个节点，m的前一个节点，m节点，n节点，n的后一个节点
        ListNode* front=NULL,*rear=NULL,*start=NULL,*end=NULL;
        int count=1;
        while(head){
            if(count==m-1){//找到了m之前的一个节点
                front=head;
            }
             if(count==m){//找到了m节点
                start=head;
            }
             if(count==n){
                end=head;
                if(head->next!=NULL)
                    rear=head->next;
                //否则直接break
                else break;
            }
            count++;
            head=head->next;
        }
        //循环结束之后四个节点的位置就全都找到了，如果front和rear没找到就是空也是对的
        end->next=NULL;//把end节点的next置为空，便于反转链表
        //接下来就是反转一个链表的固定套路
        ListNode* tmp=NULL;
        ListNode*pre=start;//先把start的值记录下来
        ListNode*qre=start->next;
        while(qre){
            start->next=tmp;
            tmp=start;
            start=qre;
            qre=start->next;
        }
        start->next=tmp;
        //现在start就是反转之后的链表的头，而现在链表的尾其实就是之前存下来的start的值
        pre->next=rear;//先将链表的后半部分连接起来，没有任何问题
        //但是链表的前半部分连接时有问题，要判断front是否为空
        if(!front)//front为空前半部分无法连接，直接返回start即可
        {
            return start;
        }
        else{
            front->next=start;
            return res;
        }
    }
    
};