Losing head/tail while rewiring
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.
A complete visual walkthrough of iterative k-group linked list reversal — from brute force to optimal O(1) space.
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]
Constraints:
n.1 <= k <= n <= 50000 <= Node.val <= 1000Follow-up: Can you solve the problem in O(1) extra memory space?
The simplest approach: copy all node values into an array, reverse every consecutive group of k values in the array, then rebuild the linked list from the modified array.
First 3 values are reversed. The last 2 values (less than k) remain in their original order. Then rebuild a new linked list from this array.
This works but uses O(n) extra space for the array. The problem specifically asks: "Can you solve the problem in O(1) extra memory space?" We need to reverse the links in-place.
The real challenge: Reversing a section of a linked list is straightforward. The tricky part is reconnecting each reversed group to the previous group and the next group without losing any references.
We process the list in groups of k nodes. For each group, we perform four sub-steps:
null before k steps, stop — the remaining nodes stay as-is.next to the previous node.groupPrev to the end of the just-reversed group (the old first node). Repeat.Why a dummy head? The first group has no "previous node." A dummy node before the head gives us a uniform groupPrev pointer for every group, including the first one. This eliminates special-case handling.
Notice how prev now points to node 3 (the new head of the group), and node 1 (the old head, now the tail) points to next (the start of the unreversed portion). The groupPrev pointer then advances to node 1.
Let's trace through [1, 2, 3, 4, 5] with k = 3 step by step.
We create a dummy node pointing to the head. groupPrev starts at the dummy.
Starting from groupPrev (dummy), walk 3 steps: dummy→1→2→3. We reach node 3, so kth = 3. Three nodes remain — proceed with reversal.
Reverse the pointers within the group. prev starts as groupNext (node 4), so node 1 will point to node 4 after reversal.
Set groupPrev.next = kth (dummy→3) and advance groupPrev to the old first node (node 1, now at the tail of the reversed group).
Starting from groupPrev (node 1), walk 3 steps: 1→4→5→null. We hit null before completing 3 steps, so kth = null. Only 2 nodes remain — not enough for a full group.
These are the scenarios you should keep in mind when implementing or testing:
getKth check fails immediately — no reversal happens. The list is returned as-is.
Constraint reminder: The problem guarantees 1 ≤ k ≤ n, so k > n won't appear in LeetCode test cases. But a robust implementation handles it anyway — and ours does, for free.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int val, ListNode next) { * this.val = val; this.next = next; * } * } */ class Solution { public ListNode reverseKGroup(ListNode head, int k) { // Dummy node simplifies head-of-list edge case ListNode dummy = new ListNode(0, head); ListNode groupPrev = dummy; while (true) { // 1. Find the k-th node from groupPrev ListNode kth = getKth(groupPrev, k); if (kth == null) break; // fewer than k nodes left // 2. Save the node after this group ListNode groupNext = kth.next; // 3. Reverse the k nodes in this group // prev starts at groupNext so the last reversed // node points to the rest of the list ListNode prev = groupNext; ListNode curr = groupPrev.next; while (curr != groupNext) { ListNode next = curr.next; // save next curr.next = prev; // reverse pointer prev = curr; // advance prev curr = next; // advance curr } // 4. Reconnect: the old first node is now the tail ListNode tmp = groupPrev.next; // old first (now tail) groupPrev.next = kth; // point to new head (kth) groupPrev = tmp; // advance to tail for next iteration } return dummy.next; } // Walk k steps from node; return null if fewer than k nodes remain private ListNode getKth(ListNode node, int k) { while (node != null && k > 0) { node = node.next; k--; } return node; } }
func reverseKGroup(head *ListNode, k int) *ListNode { // Dummy node simplifies head-of-list edge case dummy := &ListNode{Next: head} groupPrev := dummy for { // 1. Find the k-th node from groupPrev kth := getKth(groupPrev, k) if kth == nil { break } // fewer than k nodes left // 2. Save the node after this group groupNext := kth.Next // 3. Reverse the k nodes in this group // prev starts at groupNext so the last reversed // node points to the rest of the list var prev *ListNode = groupNext curr := groupPrev.Next for curr != groupNext { nxt := curr.Next // save next curr.Next = prev // reverse pointer prev = curr // advance prev curr = nxt // advance curr } // 4. Reconnect: the old first node is now the tail tmp := groupPrev.Next // old first (now tail) groupPrev.Next = kth // point to new head (kth) groupPrev = tmp // advance to tail for next iteration } return dummy.Next } // Walk k steps from node; return nil if fewer than k nodes remain func getKth(node *ListNode, k int) *ListNode { for node != nil && k > 0 { node = node.Next k-- } return node }
class Solution: def reverse_k_group( self, head: Optional[ListNode], k: int ) -> Optional[ListNode]: # Dummy node simplifies head-of-list edge case dummy = ListNode(0, head) group_prev = dummy while True: # 1. Find the k-th node from group_prev kth = self._get_kth(group_prev, k) if not kth: break # fewer than k nodes left # 2. Save the node after this group group_next = kth.next # 3. Reverse the k nodes in this group # prev starts at group_next so the last reversed # node points to the rest of the list prev = group_next curr = group_prev.next while curr is not group_next: nxt = curr.next # save next curr.next = prev # reverse pointer prev = curr # advance prev curr = nxt # advance curr # 4. Reconnect: the old first node is now the tail tmp = group_prev.next # old first (now tail) group_prev.next = kth # point to new head (kth) group_prev = tmp # advance to tail for next iteration return dummy.next # Walk k steps from node; return None if fewer than k nodes remain def _get_kth( self, node: Optional[ListNode], k: int ) -> Optional[ListNode]: while node and k > 0: node = node.next k -= 1 return node
impl Solution { pub fn reverse_k_group( head: Option<Box<ListNode>>, k: i32, ) -> Option<Box<ListNode>> { // Collect all node values into a Vec let mut vals = Vec::new(); let mut cur = &head; while let Some(n) = cur { vals.push(n.val); cur = &n.next; } // Reverse every k-length chunk in the Vec let n = vals.len(); let k = k as usize; let mut i = 0; while i + k <= n { vals[i..i+k].reverse(); i += k; } // Rebuild linked list from modified Vec let mut dummy = Box::new(ListNode::new(0)); let mut tail = &mut *dummy; for v in vals { tail.next = Some(Box::new(ListNode::new(v))); tail = tail.next.as_mut().unwrap(); } dummy.next } }
function reverseKGroup(head: ListNode | null, k: number): ListNode | null { // Dummy node simplifies head-of-list edge case const dummy = new ListNode(0, head); let groupPrev: ListNode = dummy; while (true) { // 1. Find the k-th node from groupPrev const kth = getKth(groupPrev, k); if (kth === null) break; // fewer than k nodes left // 2. Save the node after this group const groupNext = kth.next; // 3. Reverse the k nodes in this group // prev starts at groupNext so the last reversed // node points to the rest of the list let prev = groupNext; let curr = groupPrev.next; while (curr !== groupNext) { const next = curr!.next; // save next curr!.next = prev; // reverse pointer prev = curr; // advance prev curr = next; // advance curr } // 4. Reconnect: the old first node is now the tail const tmp = groupPrev.next!; // old first (now tail) groupPrev.next = kth; // point to new head (kth) groupPrev = tmp; // advance to tail for next iteration } return dummy.next; } // Walk k steps from node; return null if fewer than k nodes remain function getKth(node: ListNode | null, k: number): ListNode | null { while (node !== null && k > 0) { node = node.next; k--; } return node; }
Key detail in the reversal loop: Notice prev starts as groupNext, not null. This is what seamlessly connects the tail of the reversed group to the rest of the list. Without this, node 1 would point to null instead of node 4, breaking the chain.
Enter a list and a value for k, then step through the algorithm to see each group identified and reversed in real time.
Each node is visited at most twice: once during the getKth length check and once during the reversal. Across all n/k groups, the getKth calls walk a combined n + k steps (including the final failing check), and the reversals perform exactly n pointer swaps. Total: O(n). We use only a constant number of pointer variables -- no arrays, stacks, or recursion -- for O(1) space.
Copies all n node values into an array, reverses every k-length chunk with simple index swapping, then rebuilds a new linked list. The array allocation and the rebuilt list each use O(n) extra memory.
Each node is visited at most twice: once during the getKth length check and once during pointer reversal. Across all n/k groups this sums to O(n). Only a constant number of pointer variables (groupPrev, curr, prev, kth) are needed -- no arrays or recursion.
Even though we reverse k-length segments, each node participates in exactly one reversal, so total work is O(n). The brute force approach (copy to array, reverse chunks, rebuild list) also runs in O(n) time but requires O(n) extra space. Our in-place solution matches the time complexity with O(1) space -- exactly what the problem asks for.
Review these before coding to avoid predictable interview regressions.
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.