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
- Use a dummy head plus a size counter. The dummy removes all the special cases around the first node.
- Every operation walks from the dummy to the node before the target position.
- Keeping the size explicit makes the bounds checks O(1) and avoids traversal just to validate an index.
addAtHeadandaddAtTailare one-liners built onaddAtIndex.
💻 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
indexinstead of ignoring it inaddAtIndex: the contract is a no-op for out-of-range indices, whilegetanddeleteAtIndexreturn -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.sizeas invalid inaddAtIndex: appending at the tail is valid, so the bound isindex > self.size.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.