← Create New Paste

Reverse Nodes in k-Group (LeetCode 25): A Pointer-by-Pointer Walkthrough

5 views
Reverse Nodes in k-Group asks you to reverse a linked list k nodes at a time. If the final group has fewer than k nodes, leave it as is. For 1 -> 2 -> 3 -> 4 -> 5 with k = 2, the answer is 2 -> 1 -> 4 -> 3 -> 5; with k = 3, it is 3 -> 2 -> 1 -> 4 -> 5. You must change links, not values, and the follow-up asks for O(1) extra space. It is labeled hard mostly because of pointer bookkeeping. Break it into small, named steps and it becomes manageable. Step 1: a dummy head Create a dummy node pointing at the head. Keep a pointer group_prev that always sits just before the next group to reverse. Starting at the dummy means the first group needs no special case. Step 2: find the k-th node From group_prev, walk k steps to find kth. If you run out of nodes first, the remaining group is shorter than k and you are done. Remember group_next = kth.next, the node right after the group. Step 3: reverse the group Reverse nodes from group_prev.next up to kth, using the standard three-pointer reversal, but start prev at group_next instead of None. That way the last node of the reversed group already points to the rest of the list. Step 4: reconnect The old first node of the group is now its last node. Save it before reversing (call it first), set group_prev.next = kth, then move group_prev = first for the next iteration. Python def reverse_k_group(head, k): dummy = ListNode(0, head) group_prev = dummy while True: kth = group_prev for _ in range(k): kth = kth.next if not kth: return dummy.next group_next = kth.next first = group_prev.next prev, cur = group_next, first while cur is not group_next: nxt = cur.next cur.next = prev prev = cur cur = nxt group_prev.next = kth group_prev = first Each node is visited a constant number of times, so time is O(n) and extra space is O(1). Recursive alternative A recursive version reverses the first k nodes and calls itself on the rest. It is shorter but uses O(n/k) stack space, which breaks the follow-up constraint. Mention it, then explain why you chose the iterative version. Common bugs interviewers watch for - Reversing a short final group. Always check that k nodes exist before touching any pointers. - Losing the rest of the list. Saving group_next first prevents it. - Forgetting to move group_prev to the old first node. - Off-by-one when k = 1 (the list should be unchanged) or when k equals the length. How to present it Draw a small example with boxes and arrows before coding, and label group_prev, first, kth, and group_next. Then dry-run one group out loud. This makes the code feel like a translation of the picture, not memorized lines. Support during the interview Pointer-heavy problems are where nerves cause the most mistakes. Linkjob AI (https://linkjob.ai) provides real-time help during live job interviews and technical interviews, suggesting hints and checkpoints while you work through the solution in your own words.
Created Nov 17, 2026 17:01 Expires Nov 17, 2027 17:01