Reverse a linked list in groups of k.
/* 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.