题目形容

给你一个链表，每 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)