LeetCode: 92. Reverse Linked List II

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
	ListNode* reverseBetween(ListNode* head, int left, int right) {
		stack<int> st;
		ListNode* cur = head;
		ListNode* prev_start = nullptr;

		if (left == 1) {
			prev_start = new ListNode(0, head);  // dummy prev_start point to head
		}

		int i = 1;
		while(cur != nullptr) {
			if (i >= left && i <= right) {
				st.push(cur->val);
			}

			if ((i + 1) == left) {
				prev_start = cur;
			}

			// move ahead
			i++;
			cur = cur->next;
		}
		if (prev_start != nullptr) {
			cur = prev_start->next;
			while (st.size() > 0) {
				cur->val = st.top();
				cur = cur->next;
				st.pop();
			}
		}
		return head;
	}
};