Bird
Raised Fist0
Interview Preplinked-list-advancedhardAmazonMicrosoftGoogleFacebook

Reverse Linked List in Groups of K (Generalization)

Choose your preparation mode4 modes available
▶
Steps
setup

Initialize dummy node and pointers

Create a dummy node pointing to the head of the list. Initialize group_prev to dummy to start processing from the list head.

💡 Dummy node simplifies edge cases by providing a stable node before the head.
Line:dummy = ListNode(0) dummy.next = head group_prev = dummy
💡 Dummy node allows uniform handling of head reversal and simplifies pointer updates.
📊
Reverse Linked List in Groups of K (Generalization) - Watch the Algorithm Execute, Step by Step
Watching each pointer move and reversal operation helps you understand how groups are reversed without losing track of the list structure.
Step 1/17
·Active fill★Answer cell
advance
0
→
1
→
2
→
3
→
4
→
5
advance
0
→
1
→
2
→
3
→
4
→
5
advance
0
→
1
→
2
→
3
→
4
→
5
reverse_link
0
→
1
→
2
→
3
→
4
→
5
reverse_link
0
→
1
→
2
→
3
→
4
→
5
reverse_link
0
→
1
→
2
→
3
→
4
→
5
connect
0
→
1
→
2
→
3
→
4
→
5
advance
0
→
1
→
2
→
3
→
4
→
5
advance
0
→
1
→
2
→
3
→
4
→
5
advance
0
→
1
→
2
→
3
→
4
→
5
reverse_link
0
→
1
→
2
→
3
→
4
→
5
reverse_link
0
→
1
→
2
→
3
→
4
→
5
reverse_link
0
→
1
→
2
→
3
→
4
→
5
connect
0
→
1
→
2
→
3
→
4
→
5
advance
0
→
1
→
2
→
3
→
4
→
5
compare
0
→
1
→
2
→
3
→
4
→
5
advance
2
→
1
→
4
→
3
→
5
Result: [2, 1, 4, 3, 5]

Key Takeaways

✓ Using a dummy node simplifies handling edge cases and makes pointer manipulation consistent.

Without a dummy node, reversing the head group requires special handling, which is harder to visualize.

✓ Reversing links one node at a time with prev and curr pointers clearly shows how the group reversal works.

Seeing each pointer update step-by-step reveals the in-place reversal mechanism that is not obvious from code alone.

✓ The algorithm stops reversing when fewer than k nodes remain, leaving the last partial group intact.

This decision is critical to avoid corrupting the list and is easier to understand when watching the kth pointer traversal.

Practice

(1/5)
1. Consider the following Python code implementing an optimal linked list. After executing these operations: addAtHead(1), addAtTail(3), addAtIndex(1, 2), what is the value returned by get(1)?
easy
A. 2
B. 1
C. 3
D. -1

Solution

  1. Step 1: Trace addAtHead(1)

    List: dummy -> 1; size=1; tail points to node with val=1.
  2. Step 2: Trace addAtTail(3)

    List: dummy -> 1 -> 3; size=2; tail points to node with val=3.
  3. Step 3: Trace addAtIndex(1, 2)

    Insert 2 at index 1: dummy -> 1 -> 2 -> 3; size=3; tail remains at 3.
  4. Step 4: Trace get(1)

    Index 1 corresponds to node with val=2.
  5. Final Answer:

    Option A -> Option A
  6. Quick Check:

    Inserted 2 at index 1 correctly; get(1) returns 2 [OK]
Hint: Indexing starts after dummy node; careful with traversal loops [OK]
Common Mistakes:
  • Off-by-one in traversal loop
  • Not updating tail on addAtIndex at end
  • Returning wrong node value
2. The following code attempts to implement the two stacks browser history. Identify the line containing the subtle bug that causes forward navigation to return outdated pages after visiting a new URL.
class BrowserHistory:
    def __init__(self, homepage: str):
        self.back_stack = [homepage]
        self.forward_stack = []

    def visit(self, url: str) -> None:
        self.back_stack.append(url)
        # Missing forward_stack.clear() here

    def back(self, steps: int) -> str:
        while steps > 0 and len(self.back_stack) > 1:
            self.forward_stack.append(self.back_stack.pop())
            steps -= 1
        return self.back_stack[-1]

    def forward(self, steps: int) -> str:
        while steps > 0 and self.forward_stack:
            self.back_stack.append(self.forward_stack.pop())
            steps -= 1
        return self.back_stack[-1]
medium
A. Line where back_stack.append(url) is called in visit
B. Line where forward_stack.clear() should be called but is missing in visit
C. Line where back_stack.pop() is called in back method
D. Line where forward_stack.pop() is called in forward method

Solution

  1. Step 1: Identify visit method behavior

    Visit appends new URL but does not clear forward_stack, so forward history remains outdated.
  2. Step 2: Understand impact on forward navigation

    Without clearing forward_stack, forward() returns stale pages that should have been discarded.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Clearing forward_stack on visit is essential to maintain correct forward history [OK]
Hint: Visit must clear forward history to avoid stale pages [OK]
Common Mistakes:
  • Forgetting to clear forward stack on visit
  • Incorrectly popping from back stack
  • Mismanaging stack boundaries
3. Identify the bug in the following code snippet implementing the odd-even linked list rearrangement:
def oddEvenList(head):
    if not head or not head.next:
        return head
    odd = head
    even = head.next
    even_head = even
    while even and even.next:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next
    # Missing termination of even list
    odd.next = even_head
    return head
What is the consequence of the missing line and how to fix it?
medium
A. The function does not handle empty lists; fix by adding a check for head == None at the start
B. The odd pointer is not updated correctly inside the loop; fix by moving 'odd = odd.next' after even pointer updates
C. The even_head pointer is lost; fix by initializing even_head after the loop instead of before
D. The even list is not terminated with null, causing a cycle; fix by adding 'if even: even.next = None' before linking odd.next

Solution

  1. Step 1: Understand pointer termination

    Without setting even.next = None, the even list may still point to old nodes, causing cycles or infinite loops.
  2. Step 2: Fix by terminating even list

    Adding 'if even: even.next = None' before linking odd.next ensures even list ends properly.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Proper termination prevents cycles and infinite traversal [OK]
Hint: Always terminate the last node's next with None to avoid cycles [OK]
Common Mistakes:
  • Forgetting to terminate even list causing infinite loops
  • Misplacing pointer updates causing node skips
4. Suppose the linked list design is extended to allow negative indices in get and addAtIndex operations, where -1 refers to the last element, -2 to the second last, and so forth. Which modification correctly supports this feature without degrading average operation time complexity?
hard
A. Reject negative indices as invalid to keep implementation simple and efficient.
B. Traverse from tail backwards for negative indices to achieve O(1) access.
C. Use a doubly linked list instead of singly linked list to support backward traversal efficiently.
D. Modify get and addAtIndex to convert negative indices to positive by adding size, then proceed normally.

Solution

  1. Step 1: Understand negative index semantics

    Negative indices map to positive indices by adding the list size (e.g., -1 -> size-1).
  2. Step 2: Implement index normalization

    Convert negative indices to positive by adding size before performing normal operations, preserving O(n) traversal.
  3. Step 3: Evaluate alternatives

    Backward traversal from tail is not possible in singly linked list; doubly linked list adds complexity and space; rejecting negatives loses functionality.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    Index normalization preserves existing complexity and correctness [OK]
Hint: Normalize negative indices by adding size before operation [OK]
Common Mistakes:
  • Trying backward traversal in singly linked list
  • Switching to doubly linked list unnecessarily
  • Ignoring negative indices
5. Suppose the problem is modified so that the linked list nodes can be reused across parts (i.e., nodes can appear in multiple parts). Which of the following changes to the algorithm correctly handles this variant?
hard
A. No changes needed; the original algorithm already supports node reuse by splitting normally.
B. Modify the algorithm to skip cutting pointers and just record start nodes for each part, allowing overlap.
C. Use a hash map to track nodes already assigned and avoid duplicates during splitting.
D. Instead of cutting the list, create new nodes for each part to allow reuse without modifying the original list.

Solution

  1. Step 1: Understand node reuse requirement

    Nodes can appear in multiple parts, so original list must remain intact.
  2. Step 2: Evaluate algorithm changes

    Original algorithm cuts pointers, destroying original list structure. To allow reuse, new nodes must be created for each part.
  3. Step 3: Discard other options

    Skipping cutting pointers causes overlapping parts but does not create separate nodes. Hash map tracking is unnecessary and inefficient.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    Creating new nodes preserves original list and allows reuse [OK]
Hint: Node reuse requires copying nodes, not pointer cutting [OK]
Common Mistakes:
  • Assuming original algorithm supports reuse
  • Trying to reuse nodes without copying
  • Overcomplicating with tracking structures
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