</>EmbeddedInterview

Reverse a linked list in groups of k.

Hard"Coding: Linked Lists, Stacks & Queues"
/* reverses each block of k nodes; a final block shorter than k is left as is */
node_t *reverse_k_group(node_t *head, int k)
{
    node_t dummy = { 0, head }, *group_prev = &dummy;
    for (;;) {
        node_t *kth = group_prev;
        for (int i = 0; i < k && kth; i++) kth = kth->next;
        if (!kth) break;                          /* fewer than k nodes left */
        node_t *group_next = kth->next;
        node_t *prev = group_next, *cur = group_prev->next;
        while (cur != group_next) {               /* standard reversal inside the group */
            node_t *nx = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nx;
        }
        node_t *first = group_prev->next;         /* becomes the last node of the group */
        group_prev->next = kth;
        group_prev = first;
    }
    return dummy.next;
}
/* 1-2-3-4-5, k = 2 -> 2-1-4-3-5 */

Points: find the k-th node first so you know a full group exists; reverse within the group while linking its tail to the next group; reconnect the previous group. O(n) time, O(1) space.