Bird
Raised Fist0
Interview Preplinked-list-advancedmediumAmazonGoogleMicrosoft

Design Linked List (Full Implementation)

Choose your preparation mode4 modes available
📋
Problem

Imagine building a custom playlist manager where songs can be added, removed, or retrieved at any position efficiently. Designing a linked list from scratch is the foundation for such dynamic data structures.

Design a singly linked list with the following functionalities: - get(index): Get the value of the index-th node in the linked list. If the index is invalid, return -1. - addAtHead(val): Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. - addAtTail(val): Append a node of value val to the last element of the linked list. - addAtIndex(index, val): Add a node of value val before the index-th node in the linked list. If index equals the length of the linked list, the node will be appended to the end. If index is greater than the length, the node will not be inserted. - deleteAtIndex(index): Delete the index-th node in the linked list, if the index is valid.

0 ≤ index ≤ 10^5All values will be in the range [1, 1000]At most 10^4 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.
Edge cases: get from empty list → returns -1addAtIndex with index greater than length → no insertiondeleteAtIndex with invalid index → no deletion
</>
IDE
class MyLinkedList:class MyLinkedList {class MyLinkedList {class MyLinkedList {
class MyLinkedList:
    def __init__(self):
        # Initialize your data structure here.
        pass
    def get(self, index: int) -> int:
        pass
    def addAtHead(self, val: int) -> None:
        pass
    def addAtTail(self, val: int) -> None:
        pass
    def addAtIndex(self, index: int, val: int) -> None:
        pass
    def deleteAtIndex(self, index: int) -> None:
        pass
class MyLinkedList {
    public MyLinkedList() {
        // Initialize your data structure here.
    }
    public int get(int index) {
        return -1;
    }
    public void addAtHead(int val) {
    }
    public void addAtTail(int val) {
    }
    public void addAtIndex(int index, int val) {
    }
    public void deleteAtIndex(int index) {
    }
}
#include <iostream>
using namespace std;
class MyLinkedList {
public:
    MyLinkedList() {
        // Initialize your data structure here.
    }
    int get(int index) {
        return -1;
    }
    void addAtHead(int val) {
    }
    void addAtTail(int val) {
    }
    void addAtIndex(int index, int val) {
    }
    void deleteAtIndex(int index) {
    }
};
class MyLinkedList {
    constructor() {
        // Initialize your data structure here.
    }
    get(index) {
        return -1;
    }
    addAtHead(val) {
    }
    addAtTail(val) {
    }
    addAtIndex(index, val) {
    }
    deleteAtIndex(index) {
    }
}
0/9
Common Bugs to Avoid
Wrong: get returns -1 even for valid indicesIncorrect index validation or traversal logic stopping early.✅ Ensure traversal continues until index-th node is reached and check for None only after traversal.
Wrong: addAtIndex inserts node even when index > lengthMissing or incorrect boundary check for index in addAtIndex.✅ Add condition: if index > length, do not insert node.
Wrong: deleteAtIndex deletes node at invalid indexNo validation of index before deletion.✅ Check if index < length before deleting node.
Wrong: addAtTail causes TLE on large inputsTraversing entire list to add at tail causing O(n^2) complexity.✅ Maintain a tail pointer to add at tail in O(1) time.
Wrong: get returns wrong values after deleteAtIndexPointer updates after deletion are incorrect causing list corruption.✅ Update next pointers correctly and maintain list integrity after deletion.
✓
Test Cases
t1_01basic
Input["addAtHead(1)","addAtTail(3)","addAtIndex(1, 2)","get(1)","deleteAtIndex(1)","get(1)"]
Expected[null,null,null,2,null,3]

After adding 1 at head and 3 at tail, list is [1,3]. Adding 2 at index 1 makes list [1,2,3]. get(1) returns 2. Deleting index 1 removes 2, list becomes [1,3]. get(1) now returns 3.

t1_02basic
Input["addAtHead(5)","addAtHead(10)","addAtTail(15)","get(0)","get(2)","deleteAtIndex(1)","get(1)"]
Expected[null,null,null,10,15,null,15]

Start with empty list. addAtHead(5) -> [5], addAtHead(10) -> [10,5], addAtTail(15) -> [10,5,15]. get(0) returns 10, get(2) returns 15. deleteAtIndex(1) removes 5, list becomes [10,15]. get(1) returns 15.

t2_01edge
Input["get(0)"]
Expected[-1]

Getting from an empty list returns -1 as no nodes exist.

t2_02edge
Input["addAtIndex(1, 10)","get(0)"]
Expected[null,-1]

addAtIndex with index greater than length (0) does not insert. get(0) returns -1 since list is still empty.

t2_03edge
Input["addAtHead(1)","deleteAtIndex(1)","get(0)"]
Expected[null,null,1]

deleteAtIndex with invalid index (1) does nothing. List remains [1]. get(0) returns 1.

t3_01corner
Input["addAtHead(1)","addAtTail(2)","addAtIndex(1, 3)","get(1)","deleteAtIndex(0)","get(0)"]
Expected[null,null,null,3,null,1]

Test off-by-one errors: addAtIndex(1,3) inserts 3 between 1 and 2. get(1) returns 3. deleteAtIndex(0) removes 1, list becomes [3,2]. get(0) returns 1.

t3_02corner
Input["addAtTail(1)","addAtTail(2)","addAtTail(3)","addAtIndex(3, 4)","get(3)","deleteAtIndex(3)","get(3)"]
Expected[null,null,null,null,4,null,-1]

Test adding at index equal to length (append). addAtIndex(3,4) appends 4. get(3) returns 4. deleteAtIndex(3) removes 4. get(3) returns -1 (invalid).

t3_03corner
Input["addAtHead(1)","addAtHead(1)","addAtHead(1)","get(0)","get(1)","get(2)","deleteAtIndex(1)","get(1)"]
Expected[null,null,null,1,1,1,null,1]

All elements identical. After three insertions at head, list is [1,1,1]. get returns 1 for all valid indices. deleteAtIndex(1) removes middle node. get(1) returns 1 (last node).

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

Test with n=100 addAtTail operations to check performance. The solution must run in O(n) time per operation and complete within 2 seconds.

Practice

(1/5)
1. Given the following recursive code to convert a binary number in a linked list to an integer, what is the final output when the linked list is 1 -> 0 -> 1?
easy
A. 3
B. 7
C. 6
D. 5

Solution

  1. Step 1: Trace helper with node1 (val=1), acc=0

    acc = (0 << 1) | 1 = 1; recurse with node2
  2. Step 2: Trace helper with node2 (val=0), acc=1

    acc = (1 << 1) | 0 = 2; recurse with node3
  3. Step 3: Trace helper with node3 (val=1), acc=2

    acc = (2 << 1) | 1 = 5; recurse with None
  4. Step 4: Trace helper with None, acc=5

    Return acc=5
  5. Final Answer:

    Option D -> Option D
  6. Quick Check:

    Binary 101 equals decimal 5 [OK]
Hint: Shift and OR accumulate bits from left to right [OK]
Common Mistakes:
  • Off-by-one errors in shifting
  • Confusing bitwise OR with addition
  • Returning intermediate instead of final accumulated value
2. You are given a singly linked list and a value x. The task is to reorder the list so that all nodes with values less than x come before nodes with values greater than or equal to x, while preserving the original relative order within each partition. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?
easy
A. Extract all node values into arrays, reorder them, then rebuild the list.
B. Use two pointers to build two separate linked lists for nodes less than and greater or equal to x, then concatenate them.
C. Sort the entire linked list using merge sort and then split at value x.
D. Traverse the list once, rearranging nodes in-place by adjusting pointers without extra lists.

Solution

  1. Step 1: Understand the problem constraints

    The problem requires partitioning the list around value x while preserving relative order and achieving O(n) time and O(1) space.
  2. Step 2: Evaluate approaches

    Approach A uses extra arrays, so space is O(n). Approach B uses extra lists, so space is O(n). Approach D sorts the list, which is O(n log n) time. Only approach C rearranges nodes in-place in one pass with constant space.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    In-place rearrangement achieves O(n) time and O(1) space [OK]
Hint: In-place pointer rearrangement is O(1) space [OK]
Common Mistakes:
  • Assuming sorting is needed to partition
  • Using extra arrays or lists increases space
  • Believing two separate lists always use constant space
3. Identify the bug in the following code snippet implementing the optimal approach to copy a list with random pointers:
medium
A. Line assigning curr.next.random = curr.random.next misses null check for curr.random
B. In Step 3, copy_curr is never advanced, causing incorrect separation
C. In Step 1, new_node is linked incorrectly to curr.next
D. The function returns copy_head before fully separating the lists

Solution

  1. Step 1: Analyze Step 3 separation loop

    copy_curr is initialized but never advanced inside the loop, so copied list links are not updated correctly.
  2. Step 2: Identify fix

    Adding copy_curr = copy_curr.next inside the loop after updating copy_curr.next fixes the bug.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Without advancing copy_curr, copied list remains partially linked [OK]
Hint: Check if both original and copy pointers advance in separation loop [OK]
Common Mistakes:
  • Forgetting to advance copy_curr in separation
  • Assuming random pointer null checks are missing (they are present)
  • Mislinking new_node in Step 1 (correct here)
4. What is the space complexity of the recursive reorder list approach that uses a helper function with recursion to reorder the list in place?
medium
A. O(n) -- recursion stack uses space proportional to list length
B. O(1) -- only constant extra pointers used
C. O(log n) -- recursion depth is halved each call
D. O(n^2) -- due to repeated pointer updates in recursion

Solution

  1. Step 1: Identify recursion depth

    The helper function recurses once per node, so recursion depth is n.
  2. Step 2: Calculate space usage

    Each recursive call adds stack frame, so total space is O(n), not constant or logarithmic.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Recursion stack proportional to list length [OK]
Hint: Recursion depth equals list length -> O(n) space [OK]
Common Mistakes:
  • Assuming constant space due to in-place changes
  • Confusing recursion depth with log n
  • Overestimating to quadratic space
5. Suppose the linked list nodes can be reused multiple times (i.e., the list is cyclic or nodes appear multiple times). Which modification to the reorder list algorithm is necessary to handle this scenario correctly?
hard
A. Use a hash set to track visited nodes and avoid infinite loops during reordering.
B. No modification needed; the recursive approach handles cycles naturally.
C. Convert the list to an array first to handle duplicates, then reorder using indices.
D. Break the list into halves without reversing the second half to prevent cycles.

Solution

  1. Step 1: Understand node reuse implications

    Reusing nodes or cycles cause infinite loops if not detected during traversal.
  2. Step 2: Modify algorithm to track visited nodes

    Using a hash set to track visited nodes prevents revisiting and infinite loops.
  3. Step 3: Evaluate other options

    Recursive approach alone cannot detect cycles; array conversion adds overhead; skipping reversal breaks reorder logic.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Tracking visited nodes prevents infinite loops in cyclic lists [OK]
Hint: Cycle detection requires visited node tracking [OK]
Common Mistakes:
  • Assuming no cycles exist
  • Relying on recursion without cycle checks
  • Ignoring node reuse effects
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