TL;DR
Iterative block-by-block pointer reversal behind a dummy node — O(n) time, O(1) space (recursive version: O(n) time, O(n/k) stack).
Approach 1 — Brute force: array of nodes
Load every node into a Python list, reverse each complete k-slice of the array, then rewire all next pointers to follow the array order. It relinks real nodes (no value swapping), just with O(n) scaffolding.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
nodes = []
node = head
while node:
nodes.append(node)
node = node.next
n = len(nodes)
for start in range(0, n - n % k, k):
chunk = nodes[start:start + k]
chunk.reverse()
nodes[start:start + k] = chunk
for i in range(n - 1):
nodes[i].next = nodes[i + 1]
nodes[n - 1].next = None
return nodes[0]
Time O(n), space O(n). The constraints (n ≤ 5000) don’t kill it — the follow-up does: it uses a linear amount of extra memory precisely where the problem asks for O(1), dodging the pointer surgery being tested.
Approach 2 — Recursion, one block per call
The insight: the problem is self-similar — “reverse the first k nodes, then the answer for the rest hangs off them.” If the recursive call hands back the already-processed remainder, reversing the current block can seed its reversal with that result, and the links across the block boundary come out correct for free. (The reversal itself is the classic three-pointer prev/curr/next walk that reverses a whole list.)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# Check there are k nodes; if not, leave this tail as is.
node = head
for _ in range(k):
if not node:
return head
node = node.next
# node is now the (k+1)-th node: the next block's head.
prev = self.reverseKGroup(node, k)
curr = head
for _ in range(k):
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev
Walkthrough on [1, 2, 3, 4, 5], k = 2: the first call verifies nodes 1–2 exist and recurses from node 3. That call recurses from node 5; the deepest call sees only one node — fewer than k — and returns 5 untouched. Unwinding: the (3,4) call reverses with prev = 5, producing 4 → 3 → 5, and returns 4. The (1,2) call reverses with prev = 4, producing 2 → 1 → 4, and returns 2. Final list: [2, 1, 4, 3, 5].
Time O(n) — each node is visited by one length check and one reversal. Space O(n/k) for the recursion stack (one frame per block), which fails the strict O(1) follow-up.
Approach 3 — Iterative with a dummy node, O(1) space
The insight: all a block needs from the outside world is two anchors — group_prev, the node just before it, and group_next, the node just after its k-th node. Seed the three-pointer reversal with prev = group_next and the reversed block’s tail already points at the rest of the list; then one splice (group_prev.next = kth) attaches it in front. The block’s old head is the new group_prev. A dummy node in front of the head makes the first block a non-special case.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
group_prev = dummy
while True:
# Find the k-th node of the current block.
kth = group_prev
for _ in range(k):
kth = kth.next
if not kth:
return dummy.next # partial block: leave it, done
group_next = kth.next
# Reverse the block, seeded so its tail ends at group_next.
prev, curr = group_next, group_prev.next
while curr is not group_next:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Splice the reversed block in; old head is the new tail.
old_head = group_prev.next
group_prev.next = kth
group_prev = old_head
Walkthrough on [1, 2, 3, 4, 5], k = 2: group_prev = dummy. Block 1: kth = 2, group_next = 3; reversing 1, 2 with seed 3 yields 2 → 1 → 3; splice dummy.next = 2, group_prev = 1. List: 2, 1, 3, 4, 5. Block 2: from node 1, kth = 4, group_next = 5; reversing 3, 4 with seed 5 yields 4 → 3 → 5; splice 1.next = 4, group_prev = 3. List: 2, 1, 4, 3, 5. Block 3: the walk from node 3 hits None after one step — fewer than k nodes — so return dummy.next, i.e. [2, 1, 4, 3, 5].
Time O(n): each node is touched once by a k-th-node scan and once by a reversal. Space O(1): five pointers and a dummy node.
Common pitfalls
- Reversing the final partial block. Every approach must count k nodes before reversing; the leftover
n mod k nodes keep their order. Tests always include one.
- Losing the cross-block link. After reversal the block’s old head is its new tail and must point at the next block’s (eventually reversed) head. Seeding the reversal with
group_next (or the recursive result) handles this automatically; reversing into None and patching afterward is where most bugs live.
- Forgetting the dummy node. The list’s head changes (it becomes the first block’s k-th node); without a dummy, returning the new head and splicing the first block become special cases.
- Swapping values instead of nodes. It passes the visible tests and is explicitly banned by the problem — interviewers check for it.
Pattern takeaway
Segment-wise linked-list surgery always reduces to the same kit: a dummy node so the head is not a special case, an anchor pointer just before the segment, a “look ahead to validate the segment” scan, and the three-pointer reversal seeded with whatever should follow the segment. Master the seeded reversal — reverse into the successor rather than into None — and multi-block problems collapse into a loop of identical splices.