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

链表头插法和链表翻转

1. 头插法
2. 链表翻转

用例：

{1,2} ，3

不满K个元素时候直接原序返回，如果满足k个元素的时候，就要倒序返回，

因此 每k个元素作为一个链表，遍历的时候 要翻转过来，可以用头插法实现

剩下不足k个元素 由于要翻转过来，那么再翻转一次即可。

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head || !head->next || k <= 1) return head;
        // write code here
        ListNode H(0);
        int cnt = 0;
        ListNode* p = &H;
        ListNode* tmp = NULL;
        while (head) {
            auto t = head->next;
            head->next = NULL;
            cnt++;
            tmp = insert(tmp, head);
            head = t;
            if (cnt % k == 0) {
                p->next = tmp;
                tmp = NULL;
                while (p && p->next)
                    p = p->next;
            }
        }
        p->next = rev(tmp);
        return H.next;
    }
    ListNode* insert(ListNode* a, ListNode* b) {
        b->next = a;
        return b;
    }
    ListNode* rev(ListNode* p) {
        ListNode* pre = NULL;
        ListNode* next = NULL;
        while (p) {
            next = p->next;
            p->next = pre;
            pre = p;
            p = next;
        }
        return pre;
    }
};

#ifdef debug


int main() {
    cout << " * " << endl;
    Solution k;
    auto arr = {1, 2, 3, 3, 5};
    println (
        k.reverseKGroup(makelist({1, 2}), 3)
    );
    return 0;
}


#endif