92. 反转链表 II

链接：92. 反转链表 II - 力扣（LeetCode）

方法一：需要分类讨论

/*总体思路就是:
    pleft指向left所在的节点
    pright指向right所在的节点
    beforeleft指向left的前一个节点，或者叫做前面没有反转部分的尾节点
    behindright指向right的后一个节点，或者叫做后面没有反转部分的头节点
    然后将前后部分不反转的链表和反转的链表截断
    然后将pleft和pright之间的链表反转
    然后再将所有部分的链表连接起来
    注意在连接的时候需要分类讨论
    */
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        //相等相当于没有反转直接返回
        if(left==right)return head;
        ListNode* pleft=nullptr;
        ListNode* pright=nullptr;
        ListNode* beforeleft=nullptr;
        ListNode* behindright=nullptr;
        ListNode* p=head;
        int index=1;
        while(p)
        {
            if(index==left)pleft=p;
            if(index==left-1)beforeleft=p;
            if(index==right)
            {
                pright=p;
                break;
            }
            p=p->next;
            index++;
        }
        //满足if就是让前面不用反转的部分和反转的部分截断
        if(beforeleft!=nullptr)beforeleft->next=nullptr;
        behindright=pright->next;
        //截断要反转的链表和后面不反转的链表
        pright->next=nullptr;
        //p1接收反转后的链表的头结点
        ListNode* p1=nullptr;
        ListNode* p2=pleft;
        //p3接收反转后的链表的尾节点
        ListNode* p3=pleft;
        while(pleft)
        {
            pleft=pleft->next;
            p2->next=p1;
            p1=p2;
            p2=pleft;
        }
        //让反转后的链表的尾节点p3的下一个节点指向behindright
        p3->next=behindright;
        //如果beforeleft为空，那么p1就是整个链表的头结点
        if(!beforeleft)return p1;
        //否则就把前面没有反转部分的尾节点beforeleft的下一个节点指向p1
        beforeleft->next=p1;
        return head;
    }

方法二：不需要分类讨论，定义一个虚拟节点来解决

ListNode* reverseBetween(ListNode* head, int left, int right) {
        //相等相当于没有反转直接返回
        if(left==right)return head;
        ListNode* dummy = new ListNode(0); // 创建虚拟头节点
        dummy->next = head;
        ListNode* pleft=nullptr;
        ListNode* pright=nullptr;
        ListNode* beforeleft=dummy;//初始化为虚拟头节点
        ListNode* behindright=nullptr;
        ListNode* p=head;
        int index=1;
        while(p)
        {
            if(index==left)pleft=p;
            if(index==left-1)beforeleft=p;
            if(index==right)
            {
                pright=p;
                break;
            }
            p=p->next;
            index++;
        }
        //截断要反转的链表和后面不反转的链表
        behindright=pright->next;
        pright->next=nullptr;
        //反转链表
        //p1接收反转后的链表的头结点
        ListNode* p1=nullptr;
        ListNode* p2=pleft;
        //p3接收反转后的链表的尾节点
        ListNode* p3=pleft;
        while(pleft)
        {
            pleft=pleft->next;
            p2->next=p1;
            p1=p2;
            p2=pleft;
        }
        //让反转后的链表的尾节点p3的下一个节点指向behindright
        p3->next=behindright;
        //将前面没有反转部分的尾节点beforeleft指向反转后的链表头节点
        //因为我们通过定义一个虚节点dummy，然后将dummy->next = head;
        //然后我们给beforeleft赋值为dummy
        //那么当beforeleft不为dummy的时候，就说明前面不反转部分是有节点的
        //然后beforeleft代表这部分的尾节点，那么就把反转后的链表的头结点p1赋值给beforeleft->next
        //如果beforeleft为dummy的时，说明前面不反转的部分是没有节点的
        //那么也可以让反转后的链表的头结点p1赋值给beforeleft->next
        //这样通过虚节点就可以解决对beforeleft分类讨论的问题
        beforeleft->next = p1;
        return dummy->next;
    }