Workspace

Problem workspace

3 day streakD

Reverse Nodes in k-Group

HardLinked ListsReversal

The challenge

Reverse nodes in consecutive groups of k. Preserve the last group when it contains fewer than k nodes.

k ≥ 1; the input is acyclic. Relink nodes rather than swapping values.

Example

[1, 2, 3, 4, 5], k = 2 → [2, 1, 4, 3, 5].

Use the walkthrough below to inspect the input and each state change.

See Reverse k-group, step by step

Follow the pointers. Watch each link change.

5 nodes · singly linkedIDs = node identity · ∅ = null
Pairs; trailing node stays: Read the inputIDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links. Node positions stay fixed while arrows change. The pointer strip and node table below give the same state in text.head1A12A23A34A45A5∅
CurrentResultYellow arrow: changed next link
headA1
Inspect node links
Each row is a distinct node object. D is the dummy sentinel.
NodeValueNext
A11A2
A22A3
A33A4
A44A5
A55null
Step 01 / 23

Read the input

IDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links.

Start from the input head pointers.
View original input

A: 1 (A1) → 2 (A2) → 3 (A3) → 4 (A4) → 5 (A5); parameters: {"k":2}

Parameter indices are zero-based, except n from the end, which is one-based. Node IDs remain fixed when links change.

Put it into code

Check that the complete group exists before changing any of its links.

Node stores val and next; the random-pointer lesson adds random. C++ uses C++17 or later.

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverse_k_group(head, k):
    if k <= 1:
        return head
    dummy = Node(next=head)
    group_prev = dummy
    while True:
        kth = group_prev
        for _ in range(k):
            kth = kth.next
            if kth is None:
                return dummy.next
        group_next = kth.next
        prev, curr = group_next, group_prev.next
        while curr is not group_next:
            nxt = curr.next
            curr.next = prev
            prev, curr = curr, nxt
        old_head = group_prev.next
        group_prev.next = kth
        group_prev = old_head

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap