25 K 个一组翻转链表

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

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明：

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1

将每个组的节点保存后分组反转(不合乎常数额外空间)
空间复杂度O(k)
执行用时：12 ms
内存消耗：7.3 MB

struct ListNode *reverseKGroup(struct ListNode *head, int k)
{
    struct ListNode **arr = calloc(k * sizeof(struct ListNode *), sizeof(struct ListNode *));
    struct ListNode *node = head;
    struct ListNode hair;
    struct ListNode *step_tail = &hair;
    struct ListNode *step_head = head;
    int i;
    hair.next = head;
    while (1)
    {
        node = step_head;
        for (i = 0; i < k; i++)
        {
            if (node == NULL)
            {
                step_tail->next = step_head;
                return hair.next;
            }
            arr[i] = node;
            node = node->next;
        }
        step_head = node;
        step_tail->next = arr[k - 1];
        step_tail = arr[0];
        for (i = k - 1; i > 0; i--)
        {
            arr[i]->next = arr[i - 1];
        }
    }
}

Solution 2

将每个组的头尾节点记录后，分组反转(思路同Solution 1)
空间复杂度O(1)
执行用时：12 ms
内存消耗：6.5 MB

struct ListNode *reverseKGroup(struct ListNode *head, int k)
{
    struct ListNode *node = head;
    struct ListNode hair;
    struct ListNode *step_tail_before = &hair;
    struct ListNode *step_tail_now = &hair;
    struct ListNode *step_head_now = head;
    struct ListNode *p0, *p1, *p2;
    int i;
    hair.next = head;
    while (step_head_now != NULL)
    {
        node = step_head_now;
        for (i = 0; i < k - 1; i++)
        {
            node = node->next;
            if (node == NULL)
                goto END_WHILE;
        }
        step_tail_now = node;
        node = node->next;
        // reverse one group
        p0 = step_head_now;
        p1 = p0->next;
        for (i = 0; i < k - 1; i++)
        {
            p2 = p1->next;
            p1->next = p0;
            p0 = p1;
            p1 = p2;
        }
        // modify pointer between groups
        step_tail_before->next = step_tail_now;
        step_tail_before = step_head_now;
        step_head_now = node;
    }
END_WHILE:
    step_tail_before->next = step_head_now;
    return hair.next;
}