Reverse in Groups

Reverse nodes in groups of $k$: given $1 \to 2 \to 3 \to 4 \to 5$ and $k = 2$, produce $2 \to 1 \to 4 \to 3 \to 5$.

The pattern:

$1.$ Check if $k$ nodes remain

$2.$ Reverse those $k$ nodes

$3.$ Connect to previously processed part

$4.$ Recurse or iterate for the rest

function reverseKGroup(head, k):
    // Check if k nodes exist
    count = 0
    node = head
    while node and count < k:
        node = node.next
        count += 1
    if count < k:
        return head // don't reverse
    // Reverse k nodes, recurse for rest
    newHead = reverse(head, k)
    head.next = reverseKGroup(node, k)
    return newHead

Time: $O(n)$. Space: $O(n/k)$ for recursion, or $O(1)$ iteratively.