Bird
Raised Fist0
Interview Preplinked-list-advancedhardAmazonMicrosoftGoogleFacebook

Reverse Linked List in Groups of K (Generalization)

Choose your preparation mode4 modes available
</>
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 null;
    }
}
#include <vector>
using namespace std;

ListNode* reverseKGroup(ListNode* head, int k) {
    // Write your solution here
    return nullptr;
}
function reverseKGroup(head, k) {
    // Write your solution here
}
0/10
Common Bugs to Avoid
Wrong: [1, 2, 3, 4, 5]Code never reverses any group, returning original list always.✅ Add logic to check for k nodes and reverse groups accordingly.
Wrong: [2, 1, 4, 3, 5, 6]Code reverses only first group and leaves rest unchanged.✅ Implement loop or recursion to process all groups until end of list.
Wrong: [3, 2, 1, 5, 4]Code reverses last partial group incorrectly instead of leaving it as is.✅ Check if k nodes are available before reversal; skip reversal if fewer than k.
Wrong: [1, 2, 3, 4, 5]Code reverses nodes even when k=1, causing no change but extra operations or errors.✅ Return head immediately if k=1 to avoid unnecessary reversal.
Wrong: Timeout or stack overflowRecursive solution with large input causing stack overflow or TLE.✅ Use iterative approach with O(1) space to handle large inputs efficiently.
✓
Test Cases
t1_01basic
Input{"head":[1,2,3,4,5],"k":2}
Expected[2,1,4,3,5]

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

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

The list is reversed in groups of 3. First three nodes (1,2,3) reversed to (3,2,1), next three (4,5,6) reversed to (6,5,4).

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

Empty list input should return empty list regardless of k.

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

Single element list with k=1 should remain unchanged.

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

k equals list length, so entire list is reversed.

t2_04edge
Input{"head":[7,7,7,7,7],"k":3}
Expected[7,7,7,7,7]

All elements identical; reversal should maintain values but change node order in groups.

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

Last group has fewer than k nodes and should remain unchanged.

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

Tests correct reconnection of reversed groups; last group reversed properly.

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

Tests that no reversal occurs when k=1, a common greedy trap is to reverse anyway.

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}
⏱ Performance - must finish in 2000ms

Large input with n=100 and k=10 to test O(n) time complexity and O(1) space. Must complete within 2 seconds.

Practice

(1/5)
1. You are given a singly linked list where each node contains a binary digit (0 or 1). The linked list represents a binary number with the head as the most significant bit. Which approach guarantees an optimal solution to convert this linked list to its decimal integer value?
easy
A. Iteratively accumulate the decimal value by shifting the current value left by 1 and OR-ing with the current node's bit.
B. Use a greedy approach to pick bits that maximize the decimal value at each step.
C. Traverse the list to build a string of bits, then parse the string as a binary number.
D. Apply dynamic programming to store intermediate decimal values for sublists.

Solution

  1. Step 1: Understand the problem constraints

    The linked list represents a binary number with the head as the most significant bit, so the decimal value can be built by processing bits from left to right.
  2. Step 2: Identify the optimal approach

    Iteratively shifting the accumulated value left by 1 and OR-ing with the current bit correctly builds the decimal value in O(n) time and O(1) space, without extra string conversions or complex DP.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Bitwise accumulation matches binary to decimal conversion [OK]
Hint: Bitwise accumulation is optimal for binary to decimal conversion [OK]
Common Mistakes:
  • Using string concatenation then parsing wastes time and space
  • Greedy approaches don't apply to binary number conversion
  • Dynamic programming is unnecessary overhead here
2. You are given a singly linked list where each node contains an additional pointer that can point to any node in the list or null. The task is to create a deep copy of this list, preserving both the next and random pointer structure. Which approach guarantees an optimal solution with O(n) time and O(1) extra space?
easy
A. Interleave copied nodes within the original list, assign random pointers using the interleaved structure, then separate the lists.
B. Use a hash map to store original-to-copy node mappings and create the copy in two passes.
C. Use a recursive function with memoization to copy nodes and their random pointers.
D. Traverse the list multiple times, copying nodes and random pointers separately without extra data structures.

Solution

  1. Step 1: Understand the problem constraints

    The problem requires copying a complex linked list with random pointers efficiently.
  2. Step 2: Identify the optimal approach

    Interleaving copied nodes within the original list allows assigning random pointers without extra space, then separating the lists restores the original and creates the copy.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Interleaving nodes achieves O(n) time and O(1) space [OK]
Hint: Interleaving nodes avoids extra space for mapping [OK]
Common Mistakes:
  • Assuming recursion is always optimal
  • Using extra hash maps increases space complexity
  • Trying multiple traversals without mapping fails random pointer assignment
3. Given the following code for partitioning a linked list around value x = 3, and the input list: 1 -> 4 -> 2 -> 5, what is the final reordered list returned by the function?
easy
A. 1 -> 4 -> 2 -> 5
B. 1 -> 2 -> 4 -> 5
C. 2 -> 1 -> 4 -> 5
D. 4 -> 1 -> 2 -> 5

Solution

  1. Step 1: Trace initial pointers with input 1 -> 4 -> 2 -> 5 and x=3

    Start with dummy -> 1 -> 4 -> 2 -> 5, less_tail and prev at dummy, current at 1.
  2. Step 2: Process nodes

    Node 1 < 3, less_tail.next == current, move less_tail and prev forward. Node 4 >= 3, move prev and current forward. Node 2 < 3, less_tail.next != current, so remove 2 and insert after less_tail. Final list: 1 -> 2 -> 4 -> 5.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Nodes less than 3 appear first in original order, then others [OK]
Hint: Track less_tail and prev carefully to avoid skipping nodes [OK]
Common Mistakes:
  • Swapping values instead of nodes
  • Incorrect pointer updates causing lost nodes
  • Assuming order changes within partitions
4. You are given a singly linked list and need to reorder it so that the nodes are arranged in the sequence: first node, last node, second node, second last node, and so on. Which approach guarantees an optimal solution with O(n) time and O(1) extra space?
easy
A. Store all nodes in an array, then reorder by reassigning next pointers using two pointers from ends.
B. Use a greedy approach by alternating nodes from the start and end without modifying the list structure.
C. Use dynamic programming to store intermediate reorder states and build the final list.
D. Find the middle of the list, reverse the second half, then merge the two halves alternately.

Solution

  1. Step 1: Understand the problem constraints

    The problem requires reordering nodes in a specific pattern without extra space overhead.
  2. Step 2: Evaluate approaches for time and space

    Finding the middle, reversing the second half, and merging achieves O(n) time and O(1) space, unlike storing nodes or DP which use extra space.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Optimal approach uses middle finding and reversing [OK]
Hint: Middle + reverse + merge is classic reorder pattern [OK]
Common Mistakes:
  • Thinking greedy pointer swaps suffice
  • Using extra arrays unnecessarily
  • Confusing DP with linked list reorder
5. Suppose the linked list nodes can be reused multiple times (i.e., the list is circular or nodes can appear multiple times). Which modification to the odd-even rearrangement algorithm is necessary to handle this scenario correctly?
hard
A. Add a visited set to track nodes already processed to avoid infinite loops or duplicates
B. No modification needed; the original in-place algorithm works correctly even with reused nodes
C. Convert the list to an array first, then reorder and reconstruct the list to handle duplicates
D. Use recursion to process nodes and detect cycles automatically

Solution

  1. Step 1: Identify problem with reused nodes

    If nodes are reused or list is circular, naive pointer traversal causes infinite loops or duplicates.
  2. Step 2: Use a visited set

    Tracking visited nodes prevents revisiting and infinite loops, ensuring correct rearrangement.
  3. Step 3: Why other options fail

    No modification ignores cycles; array conversion adds overhead; recursion risks stack overflow without cycle detection.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Visited set is standard for cycle detection in linked lists [OK]
Hint: Detect cycles with visited set to avoid infinite loops [OK]
Common Mistakes:
  • Assuming original algorithm handles cycles or reused nodes
  • Using recursion without cycle detection
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard