C++ 链表k个一组翻转

思路

由于题目要求空间复杂度，说明不可以递归，那么时间复杂度就只能是了，即遍历的同时一边分组一边翻转。

这样思路就清晰了，组内直接套链表翻转的模板，组间注意要保存上一组的tail（上一组翻转前的head）。考虑最后一组不满k的情况，这时只需要再翻转一次最后一组就可以了，总体时间复杂度就是。当然，求链表长度不反转最后一组也可行。

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* last_tail;
    ListNode* reversek(ListNode* head, int k) {
        if(!head) return nullptr;
        ListNode* p = head;
        ListNode* prev = nullptr;
        int i;
        for(i = 0; i < k && p; ++i) {
            ListNode* tmp = p->next;
            p->next = prev;
            prev = p;
            p = tmp;
        }
        if(i < k) {
            return reversek(prev, i);
        }
        last_tail->next = prev;
        last_tail = head;
        return p;
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        last_tail = new ListNode(0); // 哑节点，避免对链表头做单独处理
        ListNode* res = last_tail;

        ListNode* new_head = head;
        while(new_head) {
            new_head = reversek(new_head, k);
        }
        return res->next;
    }
};