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

一、解题思路

1. 使用计数器记录左右指针移动的距离，让left和right均指针指向左区域
2. count<=n，操纵右指针指向右区域，同时将值val压栈
3. 根据栈内数据的多少决定左指针移动的位置，同时出栈将值赋给左指针指向的节点的val，完成区间值的替换

二、代码

/**
 * 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) {
        //计数器
        int count = 1;
        //栈
        stack<int> node_stack;
        ListNode* left=head;
        ListNode* right=head;
        while(count<m) {
            left=left->next;
            right=right->next;
            count++;
        }
        while(count<=n) {
            //压栈
            node_stack.push(right->val);
            right=right->next;
            count++;
        }
        while(!node_stack.empty()) {
            //出栈
            left->val=node_stack.top();
            node_stack.pop();
            left=left->next;
        }
        return head;
    }
};