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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */

    ListNode* reverseList(ListNode* head){
        if(head == nullptr || head->next == nullptr) return head;

        ListNode* lastNode = head;
        ListNode* currNode = head->next;
        ListNode* nextNode = nullptr;

        while(currNode != nullptr){
            nextNode = currNode->next;
            currNode->next = lastNode;
            lastNode = currNode;
            currNode = nextNode;
        }
        return lastNode;
    }
    
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        if(head == nullptr || m == n) return head;

        //重点：虚拟头节点（为了保证反转区间包含头节点的退化情况）
        //当反转区间包含头节点时，反转后的链表的真正头节点不再是head，
        //因此需要用vHead->next来记录反转后真正的头节点，以便返回之
        ListNode* vHead = new ListNode(0);
        vHead->next = head;

        ListNode* currNode = vHead;

        ListNode* leftBreak = nullptr; //第一段链表的结尾
        ListNode* left = nullptr; //第二段链表的开头
        ListNode* right = nullptr; //第二段链表的结尾
        ListNode* rightBreak = nullptr; //第三段链表的开头

        //按题意，第一个元素下标为1。i = 0 时，currNode = vHead
        int i = 0;
        while(currNode != nullptr){
            if(i == m-1){
                leftBreak = currNode;
                left = leftBreak->next;
            }
            else if(i == n){
                right = currNode;
                rightBreak = currNode->next;
                break;
            }
            currNode = currNode->next;
            i += 1;
        }

        //将链表切成三条
        leftBreak->next = nullptr;
        right->next = nullptr;

        //对目标区间的那一条进行反转
        reverseList(left);

        //将反转后的目标区间链表与首、尾的两段拼接
        left->next = rightBreak;
        leftBreak->next = right;

        //注意释放创建在堆区的对象
        currNode = vHead->next;
        delete vHead;
        vHead = nullptr;

        return currNode;
    }
};