题目形容

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最初残余的节点放弃原有程序。

示例 1：

输出：head = [1,2,3,4,5], k = 2
输入：[2,1,4,3,5]

示例 2：
输出：head = [1,2,3,4,5], k = 3
输入：[3,2,1,4,5]

示例 3：
输出：head = [1,2,3,4,5], k = 1
输入：[1,2,3,4,5]

翻转链表的模板

ListNode* reverseList(ListNode* head) {
    ListNode* now = NULL;
    ListNode* next = NULL;
    while(head!=NULL)
    {
        next = head->next;
        head->next = now;
        now = head;
        head = next;
    }
    return now;
}

值得记录的是，链表相干的题目中罕用的一个技巧是设置一个空的表头，就像下面代码中的 now，设置一个这样的表头可能免去一些繁琐的边界判断。

迭代法求解

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode *now, *prev, *last, *tmp;
    int cnt = 0;
    ListNode* dummy = new ListNode;
    dummy -> next = head;
    now = last = dummy;
    while(now) {
        ++cnt;
        now = now -> next;
        if(cnt == k && now) {
            prev = last -> next;
            while(--cnt) {
                tmp = last -> next;
                last -> next = tmp -> next;
                tmp -> next = now -> next;
                now -> next = tmp;
            }
            now = last = prev;
        } 
    }
    return dummy -> next;    
}

同样，咱们须要设置一个头结点免得去边界判断，在代码中体现为 dummy。因为波及到每 K 个翻转以及每一段的拼接问题，咱们不像模板中那样解决新建的头结点，而放弃 dummy 指针不动，作为最初返回答案的一个标记地位。
同时，用 now 标记每一节链表 翻转后的头 （即翻转前的尾，其实下面的 last 和 now 调换后更容易了解，这个看集体习惯），last 标记上一轮翻转后的尾结点（包含 dummy），prev 提前记录这一轮 翻转后 的尾结点（可看做是下一轮的 last）。
迭代法翻转的外围思路是 —— last（在链表中的）地位不动，以 now 为基点，顺次将各个结点插入到 now 的前面。
顺次翻转图示如下：

因为每一次翻转 while 的判断条件是 –cnt，因而每一次只需操作 k - 1 次。
容易失去 k - 1 次操作过程中，图中翻转区结点值的变动：1->2->3->4 —— 2->3->4->1 —— 3->4->2->1 —— 4->3->2->1
空间复杂度：用到 5 个辅助指针，空间复杂度为 O(1)
工夫复杂度：仅需察看 now 结点和小 while 循环次数。now 结点经验了残缺的一次遍历链表，而 while 循环共进行(k-1)*(n/k) ≈ n 次。因而相当于遍历了 2n 次，空间复杂度为 O(n)。

递归法求解

ListNode* reverseKGroup(ListNode* head, int k) {if(head == NULL || head->next == NULL || k==1)return head;
        ListNode* tail = head;
        int x = k;
        while(x) {
            tail = tail -> next;
            --x;
            if(!tail && x>0) return head;
        }
        ListNode* prev = head, *now = head -> next;
        ListNode *tmp = NULL;
        while(now && now != tail) {
            tmp = now -> next;
            now -> next = prev;
            prev = now;
            now = tmp;
        }
        head -> next = reverseKGroup(tail, k);
        return prev;
    }

递归思路即只关怀 K 个结点的翻转，而不关怀超过 K 个的其余结点。在每次翻转前，先判断结点数是否够 K 个，若足够，则进行一次翻转，若有余 K 个（以后结点 tial 为空结点，但计数未到 K——!tail&&x>0），则不需翻转，间接返回头结点。
真正做翻转操作时与翻转模板差别不大，常识尾结点变为了 tail 而不是 NULL。
递归调用时，间接令 head->next = 下一轮递归后果，而返回 prev（翻转后头结点）。
能够看到，递归法省去手动拼接过程，思路较为清晰。
空间复杂度：因为递归应用了栈，大略进行了 n / k 次递归，每次递归 O(1)复杂度，空间复杂度可示意为 O(n/k)
工夫复杂度：与迭代法雷同，进行了至少两轮遍历，复杂度为 O(n)