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

非递归：分成K组，每一组单独调用普通的链表反转函数。

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode * dummy = new ListNode(0);
        dummy->next = head;
        ListNode *pre = dummy, *temp = dummy;
        while(temp->next != nullptr)
        {
            for(int i = 0; i < k && temp != nullptr; i++)
                temp = temp->next;
            if(temp == nullptr) break;
            ListNode *oldHead = pre->next;
            ListNode *nextOldHead = temp->next;
            temp->next = nullptr;
            ListNode *newHead = reverse(oldHead);
            pre->next = newHead;
            oldHead->next = nextOldHead;
            pre = oldHead, temp = oldHead;
        }
        return dummy->next;
    }

    ListNode* reverse(ListNode *head)
    {
        ListNode *pre = nullptr, *curr = head;
        while(curr != nullptr)
        {
            ListNode *next = curr->next;
            curr->next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }
};

递归方法：

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head == nullptr || head->next == nullptr)
            return head;
        ListNode * pTail = head;
        for (int i = 0; i < k; i++)
        {
            if (pTail == nullptr)
                return head;
            pTail = pTail->next;
        }
        ListNode *newHead = reverse(head, pTail);
        head->next = reverseKGroup(pTail, k);
        return newHead;
    }

    ListNode* reverse(ListNode *head, ListNode *tail)
    {
        ListNode *pre = nullptr, *curr = head;
        while(curr != tail)
        {
            ListNode *next = curr->next;
            curr->next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }
};