[TOP202]题解 | #牛群的重新分组#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(-1); // 创建一个虚拟头节点
        dummy->next = head; // 将虚拟头节点连接到原链表头部
        ListNode* prev = dummy; // prev 指针，用于定位当前要反转的一组节点的前一个节点
        
        while (head) {
            ListNode* start = head; // 当前要反转的一组节点的第一个节点
            ListNode* end = start; // 当前要反转的一组节点的最后一个节点
            
            // 移动 end 指针到当前要反转的一组节点的最后一个节点
            for (int i = 1; i < k && end; ++i) {
                end = end->next;
            }
            
            if (!end) {
                break; // 如果不足 k 个节点，则不进行反转
            }
            
            ListNode* next = end->next; // 当前要反转的一组节点的后一个节点
            
            // 反转从 start 到 end 的一组节点
            while (start != end) {
                ListNode* temp = start->next;
                start->next = end->next;
                end->next = start;
                start = temp;
            }
            
            // 将 prev 连接到反转后的一组节点的第一个节点
            prev->next = end;
            prev = head; // 更新 prev 指针，用于连接下一组反转的节点
            head = next; // 更新 head 指针，用于遍历下一组反转的节点
        }
        
        return dummy->next; // 返回新链表的头节点
    }
};