LeetCode: 25. Reverse Nodes in k-Group

/**
 * 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* reverseKGroup(ListNode* head, int k) {
		deque<ListNode*> dq;
		ListNode* cur = head;
		ListNode* top = nullptr;
		ListNode* tail = nullptr;
		bool first_k = true;
		while (cur != nullptr) {
			dq.push_front(cur);
			cur = cur->next;

			if (dq.size() == k) {
				// start reverse in k
				top = dq.front();
				dq.pop_front();

				// override head or connected from last k
				if (first_k) {
					head = top;
					first_k = false;
				} else {
					tail->next = top;
				}

				while(!dq.empty()) {
					top->next = dq.front();
					dq.pop_front();
					top = top->next;
				}
				top->next = cur;
				tail = top; // mark the tail of linked list
			}
		}

		if (!dq.empty() && tail != nullptr) {
			tail->next = dq.back();
		}
		return head;
	}
};