Eric 的小站

1
输入：head = [1,2,3,4,5], left = 2, right = 4
2
输出：[1,4,3,2,5]

1
输入：head = [5], left = 1, right = 1
2
输出：[5]

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode() : val(0), next(nullptr) {}
7
 *     ListNode(int x) : val(x), next(nullptr) {}
8
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9
 * };
10
 */
11
class Solution {
12
public:
13
    ListNode* reverseBetween(ListNode* head, int left, int right) {
14
        stack<int> stk;
15
        ListNode *result = new ListNode();
16
        ListNode *p = head;
17
        int step = 1;
18
        while(step!=right+1){
19
            if(step>=left && step<=right){
20
                stk.push(p->val);
21
            }
22
            p = p->next;
23
            step++;
24
        }
25
        step = 1;
26
        ListNode *q = result;
27
        while(head!=nullptr){
28
            if(step>=left && step<=right)
29
            {
30
                q->next = new ListNode(stk.top());
31
                stk.pop();
32
            }else{
33
                q->next = head;
34
            }
35
            head = head->next;
36
            q = q->next;
37
            step++;
38
        }
39
        return result->next;
40
    }
41
};