Bird
Raised Fist0
Interview Preplinked-list-advancedmediumAmazonGoogleMicrosoft

Design Linked List (Full Implementation)

Choose your preparation mode4 modes available
▶
Steps
setup

Initialize dummy head, tail, and size

Create a dummy head node with value 0 and no next node. Set tail pointer to dummy and size counter to 0.

💡 Dummy head simplifies edge cases by providing a fixed start; tail pointer helps efficient tail insertions; size tracks list length for quick index validation.
Line:self.dummy = Node(0) self.tail = self.dummy self.size = 0
💡 The linked list starts empty but ready for operations with dummy and tail pointers set.
📊
Design Linked List (Full Implementation) - Watch the Algorithm Execute, Step by Step
Watching each pointer move and node change live helps you understand how linked list operations work internally, beyond just reading code.
Step 1/24
·Active fill★Answer cell
setup
0
insert
0
→
1
connect
0
→
1
connect
0
→
1
advance
0
→
1
insert
0
→
1
→
3
connect
0
→
1
→
3
advance
0
→
1
→
3
advance
0
→
1
→
3
compare
0
→
1
→
3
advance
0
→
1
→
3
insert
0
→
1
→
3
→
2
connect
0
→
1
→
3
→
2
advance
0
→
1
→
3
→
2
compare
0
→
1
→
3
→
2
advance
0
→
1
→
3
→
2
compare
0
→
1
→
3
→
2
Result: 2
compare
0
→
1
→
3
→
2
Result: 2
advance
0
→
1
→
3
→
2
Result: 2
detach
0
→
1
→
3
Result: 2
shrink
0
→
1
→
3
Result: 2
compare
0
→
1
→
3
Result: 2
advance
0
→
1
→
3
Result: 2
compare
0
→
1
→
3
Result: 3

Key Takeaways

✓ Using a dummy head node simplifies edge cases for insertions and deletions at the head.

Without dummy, special code is needed for head operations; dummy unifies logic.

✓ Maintaining a tail pointer allows O(1) insertions at the tail without traversal.

Without tail pointer, adding at tail requires traversing entire list, which is inefficient.

✓ Tracking size enables immediate index validity checks, preventing unnecessary traversal.

Size check quickly rejects invalid indices, saving time and avoiding errors.

Practice

(1/5)
1. 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
2. Given the following code snippet implementing the in-place iterative flattening of a multilevel doubly linked list, and the input list: 1 <-> 2 <-> 3, where node 2 has a child list 4 <-> 5, what is the value of curr.val after the first iteration of the outer while loop?
easy
A. 1
B. 4
C. 2
D. 3

Solution

  1. Step 1: Initial state

    curr starts at node with val=1. First iteration: curr=1, no child, move to curr.next=2.
  2. Step 2: First iteration with child

    curr=2 has child list starting at 4. The code finds tail=5, connects tail.next to curr.next (3), updates pointers, sets curr.next=4, child.prev=2, curr.child=None, then moves curr=curr.next=4.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    After first iteration, curr moves to child node 4 [OK]
Hint: After splicing child, curr moves to child's head node [OK]
Common Mistakes:
  • Assuming curr stays at original node after splicing
  • Forgetting to move curr to next after flattening
  • Confusing tail with child head
3. Given the following code snippet for splitting a linked list into k=3 parts, and the input list 1->2->3->4, what is the returned list of parts (values only)?
easy
A. [[1, 2], [3, 4], []]
B. [[1, 2], [3], [4]]
C. [[1, 2], [3], [4, None]]
D. [[1], [2], [3, 4]]

Solution

  1. Step 1: Calculate total nodes and part sizes

    Total nodes = 4, k = 3, so part_size = 1, remainder = 1. First remainder parts get one extra node.
  2. Step 2: Assign nodes to parts

    Part 0 size = 2 nodes (1,2), Part 1 size = 1 node (3), Part 2 size = 1 node (4). The returned parts are [[1,2],[3],[4]].
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Sum of parts equals original list length and sizes differ by at most one [OK]
Hint: Remainder nodes assigned to first parts -> first part larger [OK]
Common Mistakes:
  • Assigning remainder nodes to last parts
  • Off-by-one in part sizes
  • Returning fewer than k parts
4. Consider the following buggy recursive code to convert a binary number in a linked list to an integer. Which line contains the subtle bug that causes incorrect output for single-node lists?
medium
A. Line X: using addition instead of bitwise OR to accumulate bits
B. Line 7: base case check for None node
C. Line 3: __init__ method of ListNode
D. Line 9: recursive call with node.next and updated acc

Solution

  1. Step 1: Identify the accumulation operation

    The code uses bitwise OR instead of addition to combine bits: acc = (acc << 1) | node.val.
  2. Step 2: Understand impact on single-node lists

    Bitwise OR correctly sets bits without carry, ensuring accurate accumulation for all list lengths.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Bitwise OR correctly sets bits without carry, addition may overflow [OK]
Hint: Use bitwise OR, not addition, to accumulate bits [OK]
Common Mistakes:
  • Using + instead of | causes wrong bit accumulation
  • Misunderstanding bitwise operations vs arithmetic
  • Assuming addition and OR are interchangeable for bits
5. What is the time and space complexity of the optimal in-place odd-even linked list rearrangement algorithm for a list of length n?
medium
A. Time: O(n), Space: O(1) because each node is visited once and rearranged in-place
B. Time: O(n log n), Space: O(1) due to sorting nodes by index parity
C. Time: O(n), Space: O(n) due to auxiliary lists for odd and even nodes
D. Time: O(n^2), Space: O(1) because of nested pointer updates

Solution

  1. Step 1: Identify loop iterations

    The while loop advances even and odd pointers through the list, each node visited once -> O(n) time.
  2. Step 2: Analyze space usage

    No extra data structures are created; rearrangement is done by pointer manipulation -> O(1) space.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Linear time and constant space is standard for in-place linked list rearrangement [OK]
Hint: One pass with two pointers -> O(n) time, no extra lists -> O(1) space [OK]
Common Mistakes:
  • Assuming nested loops cause O(n^2) time
  • Confusing auxiliary space with recursion stack
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