- Translate each rule into one explicit state update.
- Maintain the invariant after every processed item.
- Return the accumulated state once all relevant input has been handled.
Code notes
- 56 lines of Python from the credited upstream file 707.py.
- The implementation keeps its working state in language-native values and containers.
- No explicit loop blocks detected.
Complexity
Count the number and nesting of passes over the input, then include the maintained containers in the memory estimate.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1from dataclasses import dataclass2 3 4@dataclass5class ListNode:6 val: int7 next: ListNode | None = None8 9 10class MyLinkedList:11 def __init__(self):12 self.length = 013 self.dummy = ListNode(0)14 15 def get(self, index: int) -> int:16 if index < 0 or index >= self.length:17 return -118 curr = self.dummy.next19 for _ in range(index):20 curr = curr.next21 return curr.val22 23 def addAtHead(self, val: int) -> None:24 curr = self.dummy.next25 self.dummy.next = ListNode(val)26 self.dummy.next.next = curr27 self.length += 128 29 def addAtTail(self, val: int) -> None:30 curr = self.dummy31 while curr.next:32 curr = curr.next33 curr.next = ListNode(val)34 self.length += 135 36 def addAtIndex(self, index: int, val: int) -> None:37 if index > self.length:38 return39 curr = self.dummy40 for _ in range(index):41 curr = curr.next42 temp = curr.next43 curr.next = ListNode(val)44 curr.next.next = temp45 self.length += 146 47 def deleteAtIndex(self, index: int) -> None:48 if index < 0 or index >= self.length:49 return50 curr = self.dummy51 for _ in range(index):52 curr = curr.next53 temp = curr.next54 curr.next = temp.next55 self.length -= 156