//206. 反转链表
ListNode* reverseList(ListNode* head) {
    if(head == nullptr) return head;
    ListNode* prev = nullptr;
    ListNode* curr = head;
    ListNode* next = head->next;
    while(curr != nullptr){
        curr->next = prev;
        prev = curr;
        curr = next;            
        if(next != nullptr) next = next->next;
    }
    return prev;
}

//25. K 个一组翻转链表  
ListNode* reverseKGroup(ListNode* head, int k) {
    //右移k个元素，使其next == nullptr ，复用reverseList函数
    ListNode* dummyNode = new ListNode();
    dummyNode->next = head;
    
    ListNode* lastTail = dummyNode;
    ListNode* newHead = head;
    ListNode* tail = head;
    ListNode* nextHead = head;
    while(tail != nullptr){
        int i = k;
        while(--i){
            tail = tail->next;
            if(tail == nullptr){
                lastTail->next = newHead;
                return dummyNode->next;
            } 
        }

        nextHead = tail->next;
        tail->next = nullptr;
        lastTail->next = reverseList(newHead);

        lastTail = newHead;
        newHead = nextHead;
        tail = nextHead;

    }
    return dummyNode->next;
}