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

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(!head)    return head;

        // 每一段链表的尾为向后走 K个结点，若不足 K则返回 head
        ListNode* tail = head;
        for(int i=0; i<k; i++) {
            if(!tail)    return head;
            tail = tail->next;
        }

        // 新的头即为第一次反转的返回值，尾即为原来节点的 head。
        ListNode* newHead = revers(head, tail);
        head->next = reverseKGroup(tail, k);   // 递归的调用reverseKgroup，新的头即为上一次的尾

        return newHead;
    }

    // 反转从节点 head到 tail的链表。返回值即原链表节点 tail的前一个节点。
    ListNode* revers(ListNode* head, ListNode* tail) {
        if(head==tail)    return head;

        ListNode* cur = head;
        ListNode* pre = nullptr;
        // 注意此处为 cur!=tail， 逻辑才正确。
        while(cur!=tail) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }
};