// 解题思路：
// 当 K 等于 2 的时候，此题就是两两反转链表中的值。
// 当 k 等于 N 的时候，找到区间的头尾，反转头尾这一段的链表，头尾的处理和反转两个是一样的。
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // 创建虚拟头结点
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto cur = dummy;

        // 遍历原有链表
        while(cur != nullptr)
        {
            auto end = cur;
            auto first = cur->next;

            // 检测后续结点是否有 k 个
            for(int i = 0; i < k && end != nullptr; i++)
                end = end->next;

            // 如果后续结点不足 k，直接返回即可
            if(end == nullptr)
                break;

            // 将 first ~ end 区间的所有结点依次反转
            auto p1 = first;
            auto p2 = first->next;
            while(p1 != end)
            {
                auto p2next = p2->next;
                p2->next = p1;
                p1 = p2;
                p2 = p2next;
            }

            // 将当前区间的头尾进行重新连接
            first->next = p2;
            cur->next = end;
            cur = first;
        }

        return dummy->next;
    }
};