loading

25. Reverse Nodes in k-Group — Step-by-Step Visualization

hardLeetCode #25Linked ListRecursionPointer Manipulation

Given the `head` of a linked list, reverse the nodes of the list `k` at a time, and return the modified list. `k` is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of `k` then left-out nodes, in the end, should remain as it is. You may not alter the values in the list's nodes, only nodes themselves may be changed. **Example 1:** Input: `head = [1,2,3,4,5]`, `k = 2` Output: `[2,1,4,3,5]` **Example 2:** Input: `head = [1,2,3,4,5]`, `k = 3` Output: `[3,2,1,4,5]`

Algorithm Pattern

O(1) Space Chunked Reversal

Key Idea

Process exactly k nodes at a time, manually keeping track of a pre-group and post-group pointer to seamlessly splice the reversed chunk back in.

Step-by-Step Approach

  1. Use a dummy node to anchor the generic return head. Let `groupPrev = dummy`.
  2. In a loop, scan forward `k` spots. If you hit `null`, you don't have enough nodes left; break.
  3. Mark `kth` node.
  4. Inside the group, run standard traversal reversal (`curr.next = prev`). Setting `prev` initially to `kth.next` conveniently bounds the outbound flipped edge instantly.
  5. Re-connect `groupPrev.next` to the newly established head (`kth`).
  6. Slide the anchor `groupPrev` to the newly established tail, and run loop again.

Common Gotchas

  • Losing track of the pointers across boundaries! Always grab `kth` and `groupNext` first so you don't lose the structural references during the flip.
  • Without the `tmp` tracking saving `groupPrev.next`, you'll lose the reference needed to slide `groupPrev` forward for the next iteration.

Related Problems

← All problems