题解 | #牛群的重新排列#

解题的思路：

1，先找到需要反转的片段的开始点和结束点；

2，按照节点进行正常的链表反转；

3；进行链表的拼接，有三个极端情况需要另外处理：

1）链表大小为1，或者左右标签相等；

2）左标签等于链表的第一个节点；

3）右标签等于链表的最后一个节点；

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param left int整型 
     * @param right int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        // write code here
        ListNode* CutStart = head;
        ListNode* CutEnd = head;
        ListNode* PreStart = nullptr;
        ListNode* EndNext = head;
        ListNode* act = head;
        int legth = 1;
        // 先找到要反转的片段
        for(int i = 0; act->next; i++){
            if(i < left-1){
                PreStart = CutStart;
                CutStart = CutStart->next;
            }
            if(i < right-1){
                CutEnd = CutEnd->next;
                EndNext = CutEnd->next;
            }
            act = act->next;
            legth++;
        }
        if(legth == 1 || left == right){
            return head; // 不需要反转的情况
        }
        // 进行反转
        ListNode* pre = nullptr;
        ListNode* cur = CutStart;

        while(cur != EndNext){
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        // 进行拼接
        if(right == legth){ // 处理全反转（右等于链表的最后一个）
            return pre;
        }
        if(PreStart == nullptr) // 从第一个开始反转（左等于链表的第一个）
        {
            CutStart->next = EndNext;
            return pre;
        }
        PreStart->next = pre;
        CutStart->next = EndNext;
        return head;

    }
};