LeetCode 25 · Linked List

Reverse Nodes in k-Group, explained with a picture

Reversing the train k coaches at a time.

HardLinked List
▶ Watch it step by step

The problem

Reverse the nodes of a linked list k at a time. If fewer than k nodes remain at the end, leave them as they are.

Input:  1 → 2 → 3 → 4 → 5, k = 2
Output: 2 → 1 → 4 → 3 → 5

Picture it

Picture the train divided into blocks of k coaches. For each block we first check that k coaches are really there. Then we reverse the couplings inside that block, just like reversing a whole train, and reconnect the block to what came before and what comes after. A short last block is left untouched.

How to recognise it

  • You reverse a linked list, but in blocks: each run of k nodes is reversed on its own and stays in its place.
  • A short last block (fewer than k nodes) is left alone, so you must count ahead before you start changing links.
  • Each reversed block has to be stitched to the block before it and the block after it, which means keeping a reference to the node just before the block.
  • You may change links but not values, and the follow-up asks for O(1) extra space.
  • If you can reverse a whole list (Reverse Linked List) and a section of one, this is that section reversal repeated.

Start with brute force

Put every node in a Python list, reverse each complete slice of k entries, then relink the nodes in their new order.

def reverse_k_brute(head, k):
    nodes = []
    while head:
        nodes.append(head)
        head = head.next
    full = len(nodes) - len(nodes) % k       # nodes in complete groups
    for start in range(0, full, k):
        nodes[start:start + k] = nodes[start:start + k][::-1]
    for a, b in zip(nodes, nodes[1:]):
        a.next = b
    if nodes:
        nodes[-1].next = None
    return nodes[0] if nodes else None

Time is O(n) and extra space O(n). With LeetCode's 5,000 nodes it is fast. The catch is the follow-up: solve it with O(1) extra memory, which means no array of nodes.

From brute force to the idea

  1. Find the waste. The array is only there so you can see k nodes at once. Two references can mark the block instead: the node before it (group_prev) and its last node (kth).
  2. Count before you cut. From group_prev, step k times to find kth. If you hit None first, fewer than k nodes remain: return. Nothing has been changed yet, so the short block stays as it was.
  3. Reverse inside the block. Remember nxt = kth.next, the first node after the block. Run the usual reversal, but start prev at nxt instead of None. That way the block's first node, which becomes its last, already points to the rest of the list when it is flipped.
  4. Stitch the front. Save first = group_prev.next (the old first node). Point group_prev.next at kth, the new first node.
  5. Move on. The old first node is now the block's last node, so it is the "node before" the next block: group_prev = first.

This is the key idea: count k ahead, reverse that block with prev starting at the node after it, then reconnect and repeat.

The key idea

Count k ahead, reverse that segment in place, stitch it back, repeat. O(n) time, O(1) space.

Python solution

def reverse_k(head, k):
    dummy = group_prev = Node(0, head)
    while True:
        kth = group_prev
        for _ in range(k):
            kth = kth.next
            if not kth:
                return dummy.next
        nxt = kth.next
        prev, curr = nxt, group_prev.next
        while curr is not nxt:
            curr.next, prev, curr = prev, curr, curr.next
        first = group_prev.next
        group_prev.next = kth
        group_prev = first

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n): one pass to collect, slice reversals, one pass to relinkO(n): a reference to every node
Count, reverse, stitch (shown code)O(n): each node is passed once while counting and once while reversingO(1): the dummy node and a few references

Edge cases

  • k = 1: each block of one node is "reversed" into itself, so the list is unchanged.
  • k equals the length (1 → 2 → 3, k = 3): the whole list is reversed to 3 → 2 → 1.
  • Length not a multiple of k (1 → 2 → 3 → 4 → 5, k = 3): returns 3 → 2 → 1 → 4 → 5; the last two stay in order.
  • Exact multiple (1 → 2 → 3 → 4, k = 2): returns 2 → 1 → 4 → 3, then the next count finds None and returns.
  • k larger than the length: LeetCode guarantees k ≤ n, but the shown code handles it anyway: the first count reaches None and the list is returned unchanged.
  • Node class: Node(0, head) needs a constructor that takes a value and a next node.

Common mistakes

  • Reversing first and checking the length afterwards, which reverses the short last block too.
  • Starting the reversal with prev = None. The block's last node then points to None and the rest of the list is lost.
  • Setting group_prev = kth instead of the old first node. kth is now the front of the block, so the next block gets attached in the wrong place.
  • Forgetting the dummy node, which makes the first block (whose "node before" does not exist) a special case.
Your turn: reverse the last block too

Change the rule so that the final block is reversed even if it has fewer than k nodes. For 1 → 2 → 3 → 4 → 5 with k = 3 the answer is 3 → 2 → 1 → 5 → 4. Describe your approach, then write it if you like.

Compare with our answer

No counting ahead is needed now. Reverse up to k nodes, stopping early if the list ends. Afterwards prev is the block's new front and curr is the first node after it, so stitch exactly as before.

def reverse_k_all(head, k):
    dummy = group_prev = Node(0, head)
    while group_prev.next:
        first, curr, prev = group_prev.next, group_prev.next, None
        for _ in range(k):
            if not curr:
                break
            curr.next, prev, curr = prev, curr, curr.next
        group_prev.next = prev       # last node reversed is the new front
        first.next = curr            # old front is now the block's end
        group_prev = first
    return dummy.next

Time O(n), space O(1).

A strong answer mentions: why the count-ahead step can be dropped, stopping the reversal early at None, and reconnecting both ends of each block.

Check what stuck

1. Swap every two adjacent nodes of a linked list (1 → 2 → 3 → 4 becomes 2 → 1 → 4 → 3) by relinking, in O(1) extra space. Which approach fits best?

2. Why is the shown code O(n) even though it walks k nodes ahead before reversing each block?

3. A learner writes prev, curr = None, group_prev.next. What is returned for 1 → 2 → 3 → 4 → 5 with k = 2?

Score 60% or more and the lesson is marked complete.