Reverse a linked list in groups of k

Question

Given the head of a singly linked list and an integer k, reverse the nodes k at a time and return the head. If the number of nodes is not a multiple of k, the final leftover group (fewer than k nodes) stays in its original order.

1 -> 2 -> 3 -> 4 -> 5,  k = 2   ->   2 -> 1 -> 4 -> 3 -> 5
1 -> 2 -> 3 -> 4 -> 5,  k = 3   ->   3 -> 2 -> 1 -> 4 -> 5

Do it in $O(n)$ time and $O(1)$ extra space. The recursive version is clean but uses $O(n/k)$ stack; write the iterative one.

Accepted Answer

Use a dummy head and a groupprev pointer that sits just before the group being reversed. For each group, first walk k steps to find the group's k-th node; if fewer than k nodes remain, stop and leave that tail alone. Otherwise reverse exactly the k nodes with the standard flip, then reconnect: groupprev links to the old k-th node (new head of the group), and the old first node becomes the next groupprev. Tracing 1 - 2 - 3 - 4 - 5 with k = 2: the first group (1, 2) reverses to 2 - 1 and reconnects to give 2 - 1 - 3 - 4 - 5; groupprev advances to 1. The next group (3, 4) reverses to 4 - 3, givi…

Reverse a linked list in groups of k

Your answer

More Coding questions