力扣第92题：三步定位 精准反转链表指定区间

题目解读

给定一个单链表和两个整数left与right，要求将链表中从第left个节点到第right个节点的部分进行反转，而保持其他部分不变。例如，对于链表1→2→3→4→5，left=2，right=4，反转后应为1→4→3→2→5。这个问题考察了对链表操作的熟练程度，特别是如何在不破坏链表整体结构的情况下，精确地对指定区间进行反转。

思路与过程

1.用栈结构辅助完成链表部分反转的操作。首先处理特殊情况，当left等于right时直接返回原链表。然后通过遍历链表定位四个关键节点：leftnode（反转区间起始节点）、leftlast（反转区间前一个节点）、rightnode（反转区间结束节点）和rightnext（反转区间后一个节点）。

2.找到这些关键节点后，将需要反转的区间节点依次压入栈中。然后根据left是否为1（即是否从链表头开始反转）分别处理：如果从头部开始反转，则更新链表头；否则将leftlast的next指向栈顶节点。最后依次弹出栈中节点完成反转，并将反转后的最后一个节点与rightnext连接起来。

代码与注释

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(left==right) // 特殊情况处理：不需要反转
        {
            return head;
        }
        // 定义四个关键节点指针
        ListNode* leftnode;  // 反转区间起始节点
        ListNode* leftlast;  // 反转区间前一个节点
        ListNode* rightnode; // 反转区间结束节点
        ListNode* rightnext; // 反转区间后一个节点
        ListNode* tmp=head;  // 临时指针用于遍历
        
        // 遍历链表定位关键节点
        for(int i=1;i<=right+1;i++)
        {
            if(i==left)
            {
                leftnode=tmp; // 记录反转起始节点
            }
            if(i==left-1)
            {
                leftlast=tmp; // 记录反转前一个节点
            }
            if(i==right)
            {
                rightnode=tmp; // 记录反转结束节点
            }
            if(i==right+1)
            {
                if(tmp!=rightnode)
                {rightnext=tmp;} // 记录反转后一个节点
                else
                {rightnext=nullptr;} // 处理反转到链表末尾的情况
            }
            if(tmp->next!=nullptr)
                tmp=tmp->next; // 移动指针
        }
        
        // 使用栈存储需要反转的节点
        stack<ListNode*> stk;
        while(leftnode!=rightnode->next)
        {
            stk.push(leftnode); // 压入反转区间节点
            leftnode=leftnode->next;
        }

        // 处理反转后的连接
        if(left==1) // 从链表头开始反转的情况
        {
            tmp=stk.top();
            stk.pop();
            head=tmp; // 更新链表头
        }
        else // 中间部分反转的情况
        {
            tmp=leftlast;
            tmp->next=stk.top(); // 连接反转区间前节点与反转后的第一个节点
            tmp=tmp->next;
            stk.pop();
        }

        // 完成剩余节点的反转连接
        while(!stk.empty())
        {
            tmp->next=stk.top(); // 连接反转后的节点
            tmp=tmp->next;
            stk.pop();
        }
        
        // 处理反转区间后的连接
        if(rightnext!=nullptr)
        {
            tmp->next=rightnext; // 连接反转后的最后一个节点与后续节点
        }
        else{
            tmp->next=nullptr; // 处理反转到链表末尾的情况
        }

        return head;
    }
};