LinkedList-Hard

Abstract：leetcode 链表相关 困难难度 合集

25. Reverse Nodes in k-Group

解法一

反转链表，k个一组反转，按题意模拟就行，改造原来的reverse函数，增加添加头尾的功能，会让这题简单很多

class Solution {
public:
    int getLength(ListNode* head) {
        int len = 0;
        while(head) {
            head = head->next;
            len++;
        }
        return len;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        int len = getLength(head);
        if(k > len) return head;
        ListNode* dummy = new ListNode(-1), * curr = dummy, * prev = curr;
        dummy->next = head;
        while(curr) {
            prev = curr;
            for(int i = 0; i < k; i++) {
                curr = curr->next;
                if(curr == NULL) return dummy->next;
            }
            ListNode* next = curr->next;
            curr->next = NULL;
            curr = reverse(prev->next, next, prev);
             
        }
        return dummy->next;
    }

    ListNode* reverse(ListNode* head, ListNode* tail, ListNode* front) {
        ListNode* prev = tail, *curr = head;
        while(curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        if(front) front->next = prev;
        return head;
    }
};