Repository navigation
075 — Reverse Nodes in k Group
LeetCode 25 · Hard. 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 less than or equal to the list's length. If the number of nodes remaining is not a multiple of k, leave that final group of nodes as-is, un-reversed.
This is Reverse Linked List, except instead of flipping the whole train around in one go, you're only allowed to flip it in fixed-size chunks — reverse the first k cars, leave them connected to the still-forward-facing rest of the train, then reverse the next k cars, and so on, until fewer than k cars remain, at which point that final short stretch stays untouched. Each chunk uses the exact same three-pointer flipping technique as reversing the whole list — you just have to stop after exactly k cars, remember where the next chunk starts, and stitch the tail of one flipped chunk to the head of the next.
"Reverse... k at a time" or "in groups of k" is the cue: it's a direct scaling-up of whole-list reversal, applied repeatedly to fixed-size windows instead of the entire structure at once. Whenever a problem asks for repeated partial reversals with a leftover-group exception, reach for the same prev/curr/next three-pointer walk from Reverse Linked List, bounded to k iterations per group.
Collect every node's value into an array, reverse each complete k-sized chunk of the array (leaving a shorter trailing chunk untouched), then write the rearranged values back onto the existing nodes.
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) { self.val = val }
}
func reverseKGroupBruteForce(_ head: ListNode?, _ k: Int) -> ListNode? {
var nodes: [ListNode] = []
var curr = head
while let node = curr {
nodes.append(node)
curr = node.next
}
var values = nodes.map { $0.val }
var start = 0
while start + k <= values.count {
values[start..<(start + k)].reverse()
start += k
}
for (index, node) in nodes.enumerated() {
node.val = values[index]
}
return head
}
// smoke test: 1 -> 2 -> 3 -> 4 -> 5, k = 2
let b1 = ListNode(1); let b2 = ListNode(2); let b3 = ListNode(3); let b4 = ListNode(4); let b5 = ListNode(5)
b1.next = b2; b2.next = b3; b3.next = b4; b4.next = b5
_ = reverseKGroupBruteForce(b1, 2)
var bfWalk: ListNode? = b1
while let n = bfWalk { print(n.val, terminator: " "); bfWalk = n.next } // 2 1 4 3 5Big-O: O(n) time — one pass to collect, one to reverse chunks, one to write values back. O(n) extra space for the node and value arrays.
Reverse exactly k nodes at a time using the same three-pointer technique as whole-list reversal, but only after confirming k nodes actually remain — then recursively (or iteratively) splice the result onto the next group.
func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
// Check there are at least k nodes left starting at `node`, without
// walking past what's needed.
func hasKNodes(_ node: ListNode?, _ k: Int) -> Bool {
var count = 0
var curr = node
while curr != nil && count < k {
curr = curr?.next
count += 1
}
return count == k
}
guard hasKNodes(head, k) else { return head } // fewer than k left: leave untouched
// Reverse exactly k nodes starting at head — identical to Reverse Linked
// List's prev/curr/next walk, just bounded to k steps.
var prev: ListNode? = nil
var curr = head
for _ in 0..<k {
let nextTemp = curr?.next
curr?.next = prev
prev = curr
curr = nextTemp
}
// `curr` now points to the first node of the next group (or nil).
// `head` is the original first node of this group — now its tail —
// so splice it to the (recursively) processed remainder.
head?.next = reverseKGroup(curr, k)
return prev // new head of this reversed group
}
// smoke test: 1 -> 2 -> 3 -> 4 -> 5, k = 2
let n1 = ListNode(1); let n2 = ListNode(2); let n3 = ListNode(3); let n4 = ListNode(4); let n5 = ListNode(5)
n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n5
var walk: ListNode? = reverseKGroup(n1, 2)
while let n = walk { print(n.val, terminator: " "); walk = n.next } // 2 1 4 3 5
// smoke test: 1 -> 2 -> 3 -> 4 -> 5, k = 3
let m1 = ListNode(1); let m2 = ListNode(2); let m3 = ListNode(3); let m4 = ListNode(4); let m5 = ListNode(5)
m1.next = m2; m2.next = m3; m3.next = m4; m4.next = m5
var walk2: ListNode? = reverseKGroup(m1, 3)
while let n = walk2 { print(n.val, terminator: " "); walk2 = n.next } // 3 2 1 4 5
// smoke test: k = 1 is always a no-op
let s1 = ListNode(1); let s2 = ListNode(2); let s3 = ListNode(3)
s1.next = s2; s2.next = s3
var walk3: ListNode? = reverseKGroup(s1, 1)
while let n = walk3 { print(n.val, terminator: " "); walk3 = n.next } // 1 2 3Big-O: O(n) time — each node is visited a constant number of times across the hasKNodes checks and the reversal walk. O(n / k) recursion-stack space for the recursive splice (this can be rewritten iteratively for true O(1) extra space, at the cost of manually tracking the previous group's tail).
Reverse Linked List's prev/curr/next walk doesn't care how many nodes it processes — it's already just "flip one link, then move on," and it naturally stops whenever you tell it to. So reversing in groups of k is that exact same mechanism, just bounded to run k times instead of running until the list ends. The only genuinely new piece of logic is bookkeeping: checking a full group of k nodes exists before starting to reverse (so a leftover shorter group is correctly left untouched, rather than partially reversed and unrecoverable), and remembering to splice the reversed group's original head — now sitting at its tail — onward to wherever the next group's processed result ends up. Both are direct extensions of the single-group reversal, not a new technique.
-
Linked Lists — the underlying data structure; every step here is
next-pointer rewiring, no auxiliary structure required for the optimal in-place version. -
Two Pointers — the same
prev/curr/nextthree-pointer reversal technique from Reverse Linked List, applied repeatedly, once per group ofk. -
Reverse Linked List — this problem is that one's core loop, bounded to
kiterations and repeated across the whole list with a leftover-group exception.
Reverse Nodes in k-Group is Reverse Linked List done in fixed-size batches — flip k cars at a time with the same three-pointer trick, and leave any leftover short batch untouched.
For head = [1,2,3,4,5] and k = 3, trace hasKNodes on the second recursive call (starting at node 4). Show why it returns false, and explain precisely how that false result causes nodes 4 and 5 to end up unreversed in the final output [3,2,1,4,5], even though the function already reversed the first group before making that recursive call.
⬅️ Previous: Merge k Sorted Lists · Next: Invert Binary Tree ➡️