⚡Flashcard Drill➔
NeetCode #325LC-707MediumLinked List
← Back to All Problems

#325 · #707 · Design Linked List(设计链表)

📌 Problem Statement & Constraints

Design a linked list supporting get(index), addAtHead(val), addAtTail(val), addAtIndex(index, val) and deleteAtIndex(index). get returns -1 for an invalid index; addAtIndex is a no-op for an out-of-range index. Constraints: 0 <= index, val <= 1000; at most 2000 calls.

💡 Core Algorithmic Approaches

  1. Use a dummy head plus a size counter. The dummy removes all the special cases around the first node.
  2. Every operation walks from the dummy to the node before the target position.
  3. Keeping the size explicit makes the bounds checks O(1) and avoids traversal just to validate an index.
  4. addAtHead and addAtTail are one-liners built on addAtIndex.

💻 Benchmark Python3 Implementation

class MyLinkedList:
    def __init__(self):
        self.dummy = ListNode(0)
        self.size = 0

    def _node_before(self, index: int) -> ListNode:
        prev = self.dummy
        for _ in range(index):
            prev = prev.next
        return prev

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        return self._node_before(index).next.val

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.size:
            return                     # out of range -> no-op
        prev = self._node_before(index)
        prev.next = ListNode(val, prev.next)
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        prev = self._node_before(index)
        prev.next = prev.next.next
        self.size -= 1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(index) per operation, O(1) for the size check.
💾 Space Complexity
O(n) for the nodes.

⚠️ Interview Pitfalls & Follow-ups

  • Clamping index instead of ignoring it in addAtIndex: the contract is a no-op for out-of-range indices, while get and deleteAtIndex return -1 / do nothing.
  • Forgetting the dummy head: head insertion and head deletion would need special cases.
  • Not tracking the size: bounds checks would require a traversal.
  • Using index == self.size as invalid in addAtIndex: appending at the tail is valid, so the bound is index > self.size.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems