Reverse Nodes in K-Group

📋

Reverse Nodes in K-Group

Edge cases:

</>

IDE

def reverseKGroup(head: ListNode, k: int) -> ListNode:public ListNode reverseKGroup(ListNode head, int k)ListNode* reverseKGroup(ListNode* head, int k)function reverseKGroup(head, k)

def reverseKGroup(head, k):
    # Write your solution here
    pass

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // Write your solution here
        return head;
    }
}

#include <vector>
using namespace std;

ListNode* reverseKGroup(ListNode* head, int k) {
    // Write your solution here
    return head;
}

function reverseKGroup(head, k) {
    // Write your solution here
    return head;
}

Common Bugs to Avoid

Wrong: [2, 1, 3, 4, 5]Reversing only the first group and not continuing for subsequent groups.✅ Implement a loop or recursion to process all groups until the end of the list.

Wrong: [2, 1, 4, 3, 5]Reversing partial groups at the end instead of leaving them as is.✅ Check if there are at least k nodes before reversal; if not, leave remainder unchanged.

Wrong: [1, 2, 3, 4, 5]Not reversing any nodes when k > 1 due to missing reversal logic or early return.✅ Add logic to reverse nodes in groups of k when k > 1.

Wrong: [5, 4, 3, 2, 1]Reversing entire list regardless of k groups, ignoring partial groups.✅ Reverse only in groups of k and leave last partial group as is.

Wrong: Timeout or stack overflowRecursive solution without tail recursion or inefficient repeated traversals.✅ Use iterative in-place reversal with dummy node to achieve O(n) time and O(1) space.

✓

Test Cases

Focus on handling empty and minimal input cases correctly before moving on.

Review your counting and reversal logic to avoid off-by-one and greedy mistakes.

Optimize your solution to run in linear time to handle large inputs efficiently.

t1_01basic

Input{"head":[1,2,3,4,5],"k":2}

Expected[2,1,4,3,5]

⏱ Performance - must finish in 2000ms

The list is reversed in groups of 2. The first two nodes (1,2) are reversed to (2,1), the next two nodes (3,4) reversed to (4,3), and the last node (5) remains as is.

💡 Try reversing the list in chunks of size k instead of the entire list at once.

💡 Check if there are at least k nodes before reversing each group to avoid partial reversal.

💡 Use a loop to reverse exactly k nodes and then recursively or iteratively process the rest.

Why it failed: Output differs because partial groups are reversed incorrectly or the count before reversal is not checked. Fix by verifying k nodes exist before reversal and leave remainder as is.

✓ Correctly reverses nodes in groups of k with proper boundary checks.

t1_02basic

Input{"head":[1,2,3,4,5],"k":3}

Expected[3,2,1,4,5]

⏱ Performance - must finish in 2000ms

The first three nodes (1,2,3) are reversed to (3,2,1), the remaining nodes (4,5) remain as is because they are fewer than k.

💡 Focus on reversing the first k nodes and then linking the reversed part to the rest.

💡 Ensure you do not reverse the last group if it contains fewer than k nodes.

💡 Count nodes before reversal and only reverse if count equals k.

Why it failed: Incorrect output due to reversing last partial group or failing to count nodes before reversal. Fix by adding a pre-check for k nodes before each reversal.

✓ Handles partial groups correctly by leaving them unreversed.

t2_01edge

Input{"head":[],"k":1}

Expected[]

⏱ Performance - must finish in 2000ms

Empty list input should return empty list regardless of k.

💡 Consider what happens when the input list is empty.

💡 Check if your code handles null or empty head without errors.

💡 Return head immediately if it is null or empty.

Why it failed: Fails on empty input due to null pointer or missing base case. Fix by returning head immediately if null.

✓ Correctly handles empty list input.

t2_02edge

Input{"head":[1],"k":1}

Expected[1]

⏱ Performance - must finish in 2000ms

Single node list with k=1 should remain unchanged.

💡 Check behavior when k=1, which means no reversal should happen.

💡 Verify that your code returns the original list when k=1.

💡 Add a condition to return head immediately if k equals 1.

Why it failed: Incorrect reversal when k=1 due to missing early return. Fix by returning head if k==1.

✓ Correctly returns original list when k=1.

t2_03edge

Input{"head":[1,2,3,4,5],"k":5}

Expected[5,4,3,2,1]

⏱ Performance - must finish in 2000ms

k equals list length, so entire list is reversed.

💡 Test the case where k equals the length of the list.

💡 Ensure your reversal logic can handle reversing the entire list at once.

💡 Verify that the entire list is reversed and no nodes are left unreversed.

Why it failed: Fails to reverse entire list when k equals list length due to incorrect loop or boundary condition. Fix by allowing reversal when count equals k.

✓ Successfully reverses entire list when k equals list length.

t2_04edge

Input{"head":[2,2,2,2],"k":2}

Expected[2,2,2,2]

⏱ Performance - must finish in 2000ms

All nodes have identical values; reversal should still occur correctly in groups of k.

💡 Check that reversal logic does not rely on node values but on node pointers.

💡 Ensure identical values do not cause skipping or incorrect linking.

💡 Verify that nodes are reversed by changing next pointers, not values.

Why it failed: Fails when all values are identical due to value-based logic. Fix by reversing nodes by pointers only.

✓ Correctly reverses nodes regardless of identical values.

t3_01corner

Input{"head":[1,2,3,4,5,6],"k":4}

Expected[4,3,2,1,5,6]

⏱ Performance - must finish in 2000ms

Reverses first 4 nodes, leaves last 2 nodes as is because they are fewer than k.

💡 Beware of off-by-one errors when counting nodes before reversal.

💡 Check that you only reverse when exactly k nodes are available.

💡 Use a pointer to count nodes ahead before reversal to avoid partial reversal.

Why it failed: Partial reversal of last group occurs due to off-by-one counting error. Fix by counting nodes correctly before reversal.

✓ Correctly reverses only full groups, leaving partial groups intact.

t3_02corner

Input{"head":[1,2,3,4,5],"k":2}

Expected[2,1,4,3,5]

⏱ Performance - must finish in 2000ms

Tests that the solution does not greedily reverse nodes beyond k in each group.

💡 Avoid greedy reversal of nodes beyond k in each group.

💡 Ensure reversal is limited strictly to k nodes per group.

💡 Use a loop that reverses exactly k nodes and then stops.

Why it failed: Greedy reversal beyond k nodes causes incorrect output. Fix by limiting reversal loop to k iterations.

✓ Reverses exactly k nodes per group without greediness.

t3_03corner

Input{"head":[1,2,3,4,5],"k":3}

Expected[3,2,1,4,5]

⏱ Performance - must finish in 2000ms

Checks that the solution does not confuse 0/1 knapsack style unlimited reversals with fixed k-group reversal.

💡 Remember this is a fixed k-group reversal, not unbounded reversal.

💡 Do not reuse nodes in multiple reversals or overlap groups.

💡 Reverse nodes strictly in non-overlapping groups of size k.

Why it failed: Confusing 0/1 vs unbounded reversal leads to overlapping reversals. Fix by processing non-overlapping groups only.

✓ Processes non-overlapping groups correctly without overlap.

t4_01performance

Input{"head":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"k":10}

Expectednull

⏱ Performance - must finish in 2000ms

n=100 nodes, k=10, must complete in O(n) time within 2 seconds.

💡 Aim for an O(n) time complexity solution.

💡 Avoid recursive solutions that may cause stack overflow or overhead.

💡 Use iterative in-place reversal with dummy node for efficiency.

Why it failed: TLE due to exponential or quadratic complexity from naive recursion or repeated traversals. Fix by implementing O(n) iterative reversal.

✓ Solution runs efficiently in O(n) time for large input.

Practice

1. Given the following Python code implementing the optimal recursive addition of two linked lists representing numbers in forward order, what is the value of the carry returned by addListsHelper when adding lists representing 724 and 564?

easy

A. 1

B. 2

C. 0

D. 3

Solution

1. Step 1: Trace addition from least significant digit

   Adding 4 + 4 = 8, carry 0; next 2 + 6 = 8, carry 0; finally 7 + 5 = 12, carry 1.

2. Step 2: Propagate carry backward

   Carry 1 is returned from the most significant digit addition, indicating an overflow digit.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   724 + 564 = 1288, carry 1 at MSB addition [OK]

Hint: Carry is from MSB addition overflow [OK]

Common Mistakes:

• Ignoring carry from most significant digit
• Off-by-one error in recursion base case
• Misaligning lists before addition

2. Given the following tail-recursive reversal code, what is the output printed when the input linked list is 1 -> 2 -> 3?

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head):
    def helper(prev, curr):
        if not curr:
            return prev
        next_temp = curr.next
        curr.next = prev
        return helper(curr, next_temp)
    return helper(None, head)

head = ListNode(1, ListNode(2, ListNode(3)))
new_head = reverseList(head)
curr = new_head
while curr:
    print(curr.val, end=' ')
    curr = curr.next
print()

easy

A. 3 2 1

B. 1 2 3

C. 3 1 2

D. 2 3 1

Solution

1. Step 1: Trace helper calls

   Initial call: helper(None, node1(1)) - next_temp = node2(2) - node1.next = None - call helper(node1, node2) Next call: helper(node1, node2) - next_temp = node3(3) - node2.next = node1 - call helper(node2, node3) Next call: helper(node2, node3) - next_temp = None - node3.next = node2 - call helper(node3, None) Next call: helper(node3, None) returns node3 as new head.

2. Step 2: Print reversed list

   Starting from node3, print values: 3 -> 2 -> 1

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Reversal correctly outputs 3 2 1 [OK]

Hint: Pointers reversed during recursion descent [OK]

Common Mistakes:

• Confusing original order with reversed output
• Off-by-one in pointer updates

3. Identify the bug in the following tail-recursive reversal code snippet:

def reverseList(head):
    def helper(prev, curr):
        if not curr:
            return prev
        curr.next = prev
        next_temp = curr.next
        return helper(curr, next_temp)
    return helper(None, head)

medium

A. Line 3: Base case should check if prev is None instead of curr.

B. Line 6: The recursive call should pass next_temp as prev instead of curr.

C. Line 5: next_temp is assigned after curr.next is changed, losing original next node.

D. Line 2: The helper function should be iterative, not recursive.

Solution

1. Step 1: Analyze pointer updates

   Line 5 assigns next_temp = curr.next after curr.next is set to prev, so next_temp points to prev, not the original next node.

2. Step 2: Consequence of bug

   Because next_temp is incorrect, recursion loses the rest of the list, causing incomplete reversal or infinite loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Saving next node before pointer reversal is critical [OK]

Hint: Always save next node before changing curr.next [OK]

Common Mistakes:

• Swapping order of pointer updates
• Forgetting to set head.next to None in recursion

4. The following code attempts to rotate a linked list to the right by k places. Identify the line that contains a subtle bug that can cause the list to become cyclic or truncated incorrectly.

medium

A. Line: tail.next = head # make circular

B. Line: slow.next = slow # BUG: incorrect break causing cycle

C. Line: for _ in range(k): fast = fast.next

D. Line: k = k % length

Solution

1. Step 1: Understand the purpose of breaking the list

   After rotation, the list must be broken at the new tail by setting slow.next = None.

2. Step 2: Identify the bug

   The original code sets slow.next = slow, which creates a cycle instead of breaking the list.

3. Step 3: Correct fix

   Change to slow.next = None to properly break the list.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Correct break is slow.next = None [OK]

Hint: Break list by setting slow.next = None [OK]

Common Mistakes:

• Setting slow.next to itself or wrong node causing cycles
• Not handling k modulo length correctly
• Forgetting to make list circular before rotation

5. Suppose you want to delete a node in a singly linked list given only access to that node, but now the node to delete might be the tail node. Which of the following statements is true about the optimal in-place deletion approach that copies the next node's data and deletes the next node?

hard

A. You must traverse from head to delete the tail node since no next node exists.

B. It works perfectly for tail nodes by copying data from a dummy next node.

C. You can delete the tail node by setting its value to None and next to None.

D. It cannot delete the tail node because there is no next node to copy from.

Solution

1. Step 1: Understand the limitation of the approach

   The method copies data from the next node and deletes the next node, so it requires a next node.

2. Step 2: Analyze tail node case

   The tail node has no next node, so this approach cannot be applied to delete the tail node.

3. Step 3: Consider alternatives

   Deleting the tail node requires access to the head to update the previous node's next pointer.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Tail node deletion requires head access, not possible with this method [OK]

Hint: Tail node has no next node to copy from [OK]

Common Mistakes:

• Assuming tail node can be deleted with same method
• Trying to create dummy next node to fix tail deletion
• Setting tail node value to None without pointer updates