HardLinked ListRecursion

Reverse Nodes in k-Group

1 approach, code in every language

Given the head of a singly linked list and an integer k, reverse the nodes of the list k at a time and return the modified head. Process the list in fixed-size blocks: reverse the first k nodes, then the next k, and so on.

If the number of nodes left at the end is smaller than k, leave that final group in its original order. You may only rearrange the node connections; node values must stay in place.

Example 1

Input: head = [1,2,3,4,5], k = 2

Output: [2,1,4,3,5]

The first pair and the second pair are each reversed, and the leftover node 5 stays put.

Example 2

Input: head = [1,2,3,4,5], k = 3

Output: [3,2,1,4,5]

The first three nodes are reversed while the remaining two, being fewer than k, keep their order.

Constraints

The number of nodes is n, and 1 <= k <= n <= 5000.
0 <= Node.val <= 1000

Verify Block, Reverse, Recurse

Confirm k nodes exist, reverse that block iteratively, then recursively process the rest and stitch it on.

Loading animation…

Intuition

Each group is only reversed when a full run of k nodes is available, so we first probe ahead to count them. If fewer than k remain, we return the group untouched, which naturally handles the trailing remainder. Reversing the block is the classic prev/curr pointer flip run exactly k times, which leaves the block's original head as its new tail. That old head must connect to whatever the rest of the list resolves to, so we recurse on the node right after the block. Returning the block's new front links everything together as the recursion unwinds.

Algorithm walkthrough

1Walk up to k steps from head to confirm at least k nodes are present.
2If fewer than k nodes exist, return head so the short final group stays in order.
3Reverse exactly k nodes with the prev/curr flip; prev becomes the block's new head and head becomes its tail.
4Recurse on curr (the first node after the block) to reverse the remainder.
5Attach the block's tail (the original head) to the recursion's result via head.next.
6Return prev as the new head of this reversed block.

Implementation

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        node = head
        count = 0
        while node and count < k:
            node = node.next
            count += 1
        if count < k:
            return head
        prev = None
        curr = head
        for _ in range(k):
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        head.next = self.reverseKGroup(curr, k)
        return prev

Time

O(n)

Space

O(n / k)

Each node is reversed once, and the recursion depth equals the number of full groups.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Linked List

After the pattern

Now solve one you haven't seen.

Shunting Wagon Blocks is our own problem on the technique behind Reverse Nodes in k-Group: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free