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
- 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). - Count before you cut. From
group_prev, step k times to findkth. If you hitNonefirst, fewer than k nodes remain: return. Nothing has been changed yet, so the short block stays as it was. - Reverse inside the block. Remember
nxt = kth.next, the first node after the block. Run the usual reversal, but startprevatnxtinstead ofNone. That way the block's first node, which becomes its last, already points to the rest of the list when it is flipped. - Stitch the front. Save
first = group_prev.next(the old first node). Pointgroup_prev.nextatkth, the new first node. - 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 = firstIn 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
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n): one pass to collect, slice reversals, one pass to relink | O(n): a reference to every node |
| Count, reverse, stitch (shown code) | O(n): each node is passed once while counting and once while reversing | O(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 to3 → 2 → 1. - Length not a multiple of k (
1 → 2 → 3 → 4 → 5, k = 3): returns3 → 2 → 1 → 4 → 5; the last two stay in order. - Exact multiple (
1 → 2 → 3 → 4, k = 2): returns2 → 1 → 4 → 3, then the next count findsNoneand returns. - k larger than the length: LeetCode guarantees k ≤ n, but the shown code handles it anyway: the first count reaches
Noneand 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 toNoneand the rest of the list is lost. - Setting
group_prev = kthinstead of the old first node.kthis 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.
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.
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?
Swapping pairs is k-group reversal with k = 2. Swapping values breaks the "relink nodes" rule, and the array uses O(n) space.
2. Why is the shown code O(n) even though it walks k nodes ahead before reversing each block?
Counting and reversing each touch every node of a block once, so the total is about 2n steps. Reversing a block costs O(k), not O(1).
3. A learner writes prev, curr = None, group_prev.next. What is returned for 1 → 2 → 3 → 4 → 5 with k = 2?
Node 1 becomes the block's last node and now points to None. group_prev moves to node 1, the next count finds None straight away, and the function returns 2 → 1.
Score 60% or more and the lesson is marked complete.