DSA sheet · Linked List · Reversal pattern

Reverse Nodes in k-Group

The last problem of the reversal pattern. LeetCode marks it Hard, but the teacher's point is that it is just two things we already know, joined together: Swap Nodes in Pairs (which is this problem with k = 2) and reversing a linked list with prev/curr/next. She first solves it with an array (brute force), then in place: find the k-th node, reverse the group, stitch it back, move on. Once you can draw one group being cut out, reversed and stitched back, the code writes itself.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Linked lists, the dummy node and reversal from scratch
• Part A · Brute force: values into a list, two-pointer reverse each group, write back
• Part B · Optimal: cut, reverse and stitch each group in place
• Part C · Revision page

Part 0 · Before starting

Nodes, head and None

A linked list is a chain of nodes. Each node holds a value (val) and an arrow to the next node (next). The last arrow points to None, the end of the chain. The first node is the head, the only way into the list.

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

[1] → [2] → [3] → [4] → [5] → None
 ↑
head

Walking, and why there is no index

There is no list[3] in a linked list. To reach the 4th node you start at head and follow 3 arrows: curr = curr.next, again and again. Reaching position i costs O(i) steps. Always walk with a helper like curr; never move head itself, or you lose the start of the list.

curr = head
while curr is not None:
    # use curr.val
    curr = curr.next

Save next before you change it

A node only knows its own next node. The moment you overwrite curr.next, the old next node is unreachable unless you stored it in a variable first. That one rule is the whole reversal trick.

Reversing a list with prev / curr / nxt

To reverse, every arrow must turn around. We walk with three pointers:

• curr: the node whose arrow we are turning now.
• prev: the node that arrow should point to after turning.
• nxt: a saved copy of curr.next, so we can still move forward after the arrow is turned.

prev = None
curr = head
while curr is not None:     # stop when we fall off the end
    nxt = curr.next         # 1. save the way forward
    curr.next = prev        # 2. turn the arrow back
    prev = curr             # 3. prev steps forward
    curr = nxt              # 4. curr steps forward (using the saved copy)
# prev is now the new head

start:      None   [1] → [2] → [3] → None
             ↑      ↑
            prev   curr

after 1st:  None ← [1]   [2] → [3] → None
                    ↑     ↑
                   prev  curr

after 3rd:  None ← [1] ← [2] ← [3]    None
                                ↑      ↑
                               prev   curr  → stop, new head = 3

Two details matter for this problem: (1) the loop stops at None because we reverse "until the end"; (2) prev starts as None because the old first node becomes the last node and must point to the end. In Part B we will change both: stop at the next group instead of None, and start prev at the next group instead of None.

The dummy node

A dummy is a fake node placed before the head: dummy = ListNode(0, head). Here the head changes (the first group gets reversed, so its last node becomes the new head). With a dummy, the first group has a node in front of it just like every later group does, so no special case is needed, and the answer is always dummy.next. The teacher notes you could avoid the dummy with extra base-case code, but she always prefers the dummy because it's easier.

Part A · Brute force: reverse groups in an array

LeetCode 25 · Reverse Nodes in k-Group

1The question in simple words

You get the head of a list and a number k. Cut the list into groups of k nodes from the left. Reverse each full group. If the last group has fewer than k nodes, leave it as it is. Return the new head.

before: [1] → [2] │ [3] → [4] │ [5]
after:  [2] → [1] → [4] → [3] → [5] → None
                              5 alone: left as is

before: [1] → [2] → [3] │ [4] → [5]
after:  [3] → [2] → [1] → [4] → [5] → None
                          4, 5: only 2 nodes, not reversed

With k = 2 the answer is exactly what Swap Nodes in Pairs gives. The new part is that k can be any number.

2What the constraints tell us

• Number of nodes n: up to 5000 (5 × 10³). Even O(n²) = 25 × 10⁶ would be under the ~10⁸ TLE line. But linked list solutions are usually linear anyway, with or without extra space.
• 1 ≤ k ≤ n → k can be 1. Groups of size 1 reversed are unchanged, so we can return head straight away.
• The teacher also guards head is None (empty list) in her base case. With k ≤ n the list can't really be empty, but the guard costs nothing.

3Intuition: if it were an array

Pretend we had a Python list. Each group starts at index i and ends at index i + k − 1. Reversing one piece of an array is the classic two-pointer trick: put left at the start and right at the end, swap them, move both inward, stop when they meet.

index:  0   1   2   3   4          k = 3
arr:   [1,  2,  3,  4,  5]
        L       R              swap 1,3 → [3, 2, 1, 4, 5]
            L R                L == R → stop (middle stays)
next group: i = 3, end = 3+3-1 = 5 → out of range → stop

4Building the logic

How does i move? i++ or i += k?

After one group is done, the next group starts k places later, so i += k, not i += 1.

When is a group "full"?

A group from i needs index i + k − 1 to exist. That's the same as i + k ≤ n. In the k = 3 example, i = 3 gives 3 + 3 = 6 > 5, so the group (4, 5) is short and the loop stops. That's how the "leave the last short group alone" rule comes for free.

Is it O(n²) because of a loop inside a loop?

The teacher warns against this guess. The outer loop runs only n / k times (once per group). The inner two-pointer loop does k / 2 swaps per group. Total swaps: (n / k) × (k / 2) = n / 2. So it's linear.

Turning it into a linked list solution

Walk the list with curr and copy the values into an array. Reverse the groups in the array. Walk the list again and overwrite each node's value. For 1→2→3→4→5, k = 3, we write 3, 2, 1, 4, 5 into the same five nodes and return head.

5Approach steps

1. If head is None or k == 1 → return head.
2. Copy all values into arr.
3. For i = 0, k, 2k, … while i + k ≤ len(arr): set left = i, right = i + k − 1, and swap inward while left < right.
4. Write arr back into the nodes from the head.
5. Return head.

6Code (Python)

class Solution:
    def reverseKGroup(self, head, k):
        if head is None or k == 1:          # nothing to reverse
            return head

        arr = []
        curr = head
        while curr is not None:             # copy values out
            arr.append(curr.val)
            curr = curr.next

        i = 0
        while i + k <= len(arr):            # only full groups
            left, right = i, i + k - 1
            while left < right:             # two-pointer reverse
                temp = arr[left]
                arr[left] = arr[right]
                arr[right] = temp
                left += 1
                right -= 1
            i += k                          # jump to the next group

        curr = head
        idx = 0
        while curr is not None:             # write values back
            curr.val = arr[idx]
            idx += 1
            curr = curr.next
        return head

7Code line by line

8Dry run: 1 → 2 → 3 → 4 → 5, k = 3

9Complexity & remember

• Time O(n): n (copy) + n/2 (swaps) + n (write back) = 5n/2.
• Space O(n): the array.

Part B · Optimal: cut, reverse and stitch in place

LeetCode 25 · O(1) extra space

1The question in simple words

Same question, but now really move the nodes by changing arrows, with no extra array.

2What the constraints tell us

• k can be 1 → keep the quick return (the in-place code would also work, it would just "reverse" groups of one).
• k ≤ n, but the last group can still be short, so we must check that k nodes exist before reversing each group.

3Intuition: four labelled spots around each group

For every group we name four places (example 1→2→3→4→5, k = 3):

[0] → [1] → [2] → [3] → [4] → [5] → None
 ↑     ↑           ↑     ↑
 │     │           │     group_next  (first node AFTER the group)
 │     │           kth   (last node of the group, found by k jumps)
 │     first node of the group = prev_group.next
prev_group  (node just BEFORE the group; the dummy for group 1)

The plan for one group is a three-step story:

1. Find the cut. Starting from prev_group, jump k times to reach kth. If we fall off the list (None) before k jumps, this group is short: stop.
2. Reverse inside the cut. Run the normal reversal, but stop when curr reaches group_next (not None), and start prev at group_next (not None), so the old first node ends up pointing straight to the rest of the list.
3. Stitch the left side. Make prev_group.next point to kth (the new front of the group). Then the old first node, now at the back of the group, becomes prev_group for the next round.

4Building the logic from the teacher's drawing

Why do we need to reach the k-th node?

After reversing (1, 2, 3), the list must read 0 → 3 → 2 → 1 → 4. So 1 must point to 4, and the dummy must point to 3. Both 3 and 4 are k steps away from the dummy, so we walk there. The teacher first calls this walker curr, then renames it kth, because the name curr is needed for the reversal.

kth = prev_group
for _ in range(k):
    kth = kth.next
    if kth is None:          # fewer than k nodes left
        return dummy.next    # leave this group as it is

Once we have kth, the node after the group is group_next = kth.next (4 here).

Why does prev start at group_next?

The teacher reasons node by node about where each arrow must point after the reversal:

• 3 must point to 2, so when we turn 3's arrow, prev must be 2.
• 2 must point to 1, so when we turn 2's arrow, prev must be 1.
• 1 must point to 4, so when we turn 1's arrow (the very first turn), prev must be 4, which is group_next.

In plain reversal prev starts at None because the first node becomes the tail of the whole list. Here the first node becomes the tail of the group, and it must hand over to the rest of the list. So prev = group_next, and curr = prev_group.next (node 1).

When does the reversal loop stop?

Reverse 1, reverse 2, reverse 3, and at 4 stop, because 4 belongs to the next group. 4 is exactly group_next, which is why it got its own name. So the loop is while curr is not group_next. The four lines inside are the usual ones: save next, turn the arrow, move prev, move curr = saved next (not curr.next, which now points backwards).

Snapshots of the cut-reverse loop (group 1, k = 3)

before the loop:   prev = group_next = [4],  curr = [1]
[0] → [1] → [2] → [3] → [4] → [5] → None
 ↑     ↑           ↑     ↑
 pg   curr        kth   group_next = prev

turn 1 (curr = 1):  1.next = 4
[0] → [1] → [4] → [5] → None
      [2] → [3] → [4]           (2 still leads on to 3)
prev = [1], curr = [2]

turn 2 (curr = 2):  2.next = 1
[0] → [1] → [4] → [5] → None
[2] → [1]                       (2 now points back to 1)
[3] → [4]
prev = [2], curr = [3]

turn 3 (curr = 3):  3.next = 2
[3] → [2] → [1] → [4] → [5] → None     (dummy [0] still → [1])
prev = [3] = kth, curr = [4] = group_next → loop stops

The missing stitch on the left

Now read the list from the dummy: 0 → 1 → 4 → 5. Where did 3 and 2 go? They're fine (3 → 2 → 1 → 4 → 5), but the dummy still points to 1. The dummy must point to the new front of the group, which is kth (3):

Where is prev_group for the next group?

For group (4, 5, 6) the node just before it is 1, the old first node of this group, now its last. Can we use head to find it? Only for the first group: head is always node 1, but for group (7, 8, 9) we'd need node 4. So the teacher saves the old first node in a temp variable before the left stitch overwrites prev_group.next:

temp = prev_group.next     # old first node (1); it's the group's tail now
prev_group.next = kth      # left side now points to the new front (3)
prev_group = temp          # 1 is the node before the next group

The outer loop and the return

We repeat "find kth → reverse → stitch" for as long as full groups exist. The teacher writes it as while True and breaks out when kth becomes None. At the end, return dummy.next: head is still node 1, and returning it would give 1 → 4 → 5, losing 3 and 2.

5Approach steps

1. If head is None or k == 1 → return head.
2. dummy = ListNode(0, head), prev_group = dummy.
3. Loop forever: walk kth k steps from prev_group. If it hits None → break.
4. group_next = kth.next.
5. prev = group_next, curr = prev_group.next; while curr is not group_next: save next, curr.next = prev, prev = curr, curr = saved.
6. temp = prev_group.next; prev_group.next = kth; prev_group = temp.
7. Return dummy.next.

6Code (Python)

class Solution:
    def reverseKGroup(self, head, k):
        if head is None or k == 1:
            return head

        dummy = ListNode(0, head)
        prev_group = dummy                  # node before the current group

        while True:
            # 1. find the k-th node of this group
            kth = prev_group
            for _ in range(k):
                kth = kth.next
                if kth is None:
                    break
            if kth is None:                 # short group: leave it
                break

            group_next = kth.next           # first node after the group

            # 2. reverse the group; first node will point to group_next
            prev = group_next
            curr = prev_group.next
            while curr is not group_next:
                nxt = curr.next
                curr.next = prev
                prev = curr
                curr = nxt

            # 3. stitch the left side and move to the next group
            temp = prev_group.next          # old first node = new group tail
            prev_group.next = kth           # kth is the new group front
            prev_group = temp

        return dummy.next

7Code line by line

8Dry run: 1 → 2 → 3 → 4 → 5 → 6 → 7, k = 3

Expected answer: 3 → 2 → 1 → 6 → 5 → 4 → 7 (two full groups, 7 left alone).

[0] → [1] → [2] → [3] → [4] → [5] → [6] → [7] → None
 ↑     ↑           ↑     ↑
pg    curr        kth   group_next = prev

[0] → [3] → [2] → [1] → [4] → [5] → [6] → [7] → None
                   ↑     ↑           ↑     ↑
                  pg    curr        kth   group_next

[0] → [3] → [2] → [1] → [6] → [5] → [4] → [7] → None
                                     ↑     ↑      ↑
                                    pg    jump1  jump2 = None → stop

9Complexity & remember

• Time O(n): each node is visited a constant number of times (once by the k-jump search, once by the reversal). The short tail is only scanned, never reversed.
• Space O(1): a handful of pointers and one dummy node.

The teacher's warning: if reversing a list isn't automatic for you yet, this problem will feel hard. Go back to plain reversal and Swap Nodes in Pairs, then come back.

Part C · Revision page

def build(vals):
    dummy = ListNode()
    tail = dummy
    for v in vals:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

s = Solution()
print(to_list(s.reverseKGroup(build([1, 2, 3, 4, 5]), 2)))        # [2, 1, 4, 3, 5]
print(to_list(s.reverseKGroup(build([1, 2, 3, 4, 5]), 3)))        # [3, 2, 1, 4, 5]
print(to_list(s.reverseKGroup(build([1, 2, 3, 4, 5, 6, 7]), 3)))  # [3, 2, 1, 6, 5, 4, 7]
print(to_list(s.reverseKGroup(build([1, 2, 3]), 3)))              # [3, 2, 1]
print(to_list(s.reverseKGroup(build([1, 2]), 1)))                 # [1, 2]

Based on this video: Reverse Nodes in k-Group