25

題目:
https://leetcode.com/problems/reverse-nodes-in-k-group/description/

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* start = head;
        ListNode* end = teamEnd(head, k);
        if(end == nullptr) return head; // no need to reverse

        head = end; // new head is previous end

        rev(start, end); // remember : start is end, end is start now.
        ListNode* lastTeamEnd = start; // new end is initial head
        while(lastTeamEnd->next != nullptr){ // there is still items in list
            start = lastTeamEnd->next; // now, start is the first of the sublist
            end = teamEnd(start, k); // then end is the kth of the sublist
            if(end == nullptr) return head; // if end's pos < k, means we can't reverse anymore, return

            rev(start, end); // else, reverse the sublist
            lastTeamEnd->next = end; // we need to connect the last team's end to new start (which is "end" after reverse)
            lastTeamEnd = start; // then last team end is "start" after reverse
        }

        return head; // return the head node
    }

    ListNode* teamEnd(ListNode* head, int k){
        while(--k > 0 && head != nullptr){ // head itself counts 1 of course, so we check --k instead of k--
            head = head->next; // head keeps going until it goes for length k or it can't go anymore
        }
        return head;
    }

    void rev(ListNode* start, ListNode* end){
        ListNode* nextTeamStart = end->next; // we record the nextTeamStart, which is end->next
        ListNode *pre = nullptr, *curr = start, *next = nullptr;
        // classic linked list reverse
        while(curr != nextTeamStart){
            next = curr->next;
            curr->next = pre;
            pre = curr;
            curr = next;
        }
        start->next = nextTeamStart;
    }
};