题解 | 链表中的节点每k个一组翻转

可以根据喜好选择写法。

class Solution {
public:
    ListNode* reverseList(ListNode* head, ListNode* tail) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != tail) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev; // 返回新头节点
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        if (k == 1) return head;
        ListNode dummy(0);
        dummy.next = head;
        ListNode* pre = &dummy;
        ListNode* curr = head;
        
        while (curr) {
            // 找到当前分组的尾节点
            ListNode* tail = pre;
            for (int i = 0; i < k; ++i) {
                tail = tail->next;
                if (!tail) return dummy.next; // 不足k个，直接返回
            }
            // 保存下一组的起始节点
            ListNode* next_group = tail->next;
            // 反转当前分组
            pre->next = reverseList(pre->next, tail->next);
            // 连接反转后的尾节点到下一组
            curr->next = next_group;
            // 更新pre和curr
            pre = curr;
            curr = next_group;
        }
        return dummy.next;
    }
};

class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        if (k == 1) return head;
        ListNode dummy(0);
        dummy.next = head;
        int n = 0;
        while (head) {
            n++;
            head = head->next;
        }
        head = dummy.next;
        ListNode *pre = &dummy;
        ListNode *curr = head;
        ListNode *start = curr;
        ListNode *prev = nullptr;
        ListNode *tmp;

        while (n >= k) {
            for (int i = 0; i < k; ++i) {
                tmp = curr->next;
                curr->next = prev;
                prev = curr;
                curr = tmp;
            }
            //操作结束后，prev是反转后的开头，curr是反转部分的下一个结点
            pre->next = prev;
            start->next = curr;

            pre=start;
            start=curr;
            prev=nullptr;

            n -= k;
        }
        return dummy.next;
    }
};