K 个一组翻转链表，每 k 个节点一组进行翻转，请你返回翻转后的链表

Question

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

力扣 https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

Answer 1

一、分析

分几步吧，首先实现一个链表反转的接口，然后实现一个每k个结点截断的接口。
一段一段的就进行反转，反转利用递归实现。

二、源码

struct ListNode* reverseList(struct ListNode *l) {
    struct ListNode *pre = l, *now = l->next;
    struct ListNode *head = l;
    while(now) {
        pre->next = now->next;       // (1) 将 now 从链表中剥离出来；
        now->next = head;            // (2) 将 now 插入到之前的链表头之前；
        head = now;                  // (3) 让 now 成为新的链表头；
        
        now = pre->next;             // (4) now 也前进一格；
    }
    return head;
}

// 返回第 k 个 node，不存在这返回 NULL;
struct ListNode* KLastNode(struct ListNode *l, int k) {
    int cnt = 0;
    while (l) {
        ++cnt;
        if(cnt >= k) {
            return l;
        }
        l = l->next;
    }
    return NULL;
}

struct ListNode* reverseKGroup(struct ListNode* head, int k){
    struct ListNode *node = KLastNode(head, k);
    struct ListNode *tmp, *last;
    if(!node) {
        return head;
    }
    tmp = reverseKGroup(node->next, k);
    node->next = NULL;
    last = head;
    head = reverseList(head);
    last->next = tmp;
    return head;
}