可以选择使用单链表或者双链表，设计并实现自己的链表。 单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。 如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。 提示： 0 <= index, val <= 1000 请不要使用内置的 LinkedList 库。 调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。 ```python class ListNode: # 没必要双链表 def __init__( self, val=0, next=None ): self.val = val self.next = next class MyLinkedList: def __init__(self): self.dummy_head = ListNode() # 方便头部插入 self.tail = self.dummy_head # 方便尾部插入 self.size = 0 # 统计链表长度 def get(self, index: int) -> int: if index >= 0 and index < self.size: cur = self.dummy_head for i in range( index + 1 ): cur = cur.next return cur.val return -1 def addAtHead(self, val: int) -> None: if self.size == 0: return self.addAtTail( val ) node = ListNode( val ) node.next = self.dummy_head.next self.dummy_head.next = node self.size += 1 return self.dummy_head.next def addAtTail(self, val: int) -> None: node = ListNode( val ) self.tail.next = node self.size += 1 self.tail = node return self.dummy_head.next def addAtIndex(self, index: int, val: int) -> None: if index >= 0 and index <= self.size: if index == 0: return self.addAtHead( val ) if index == self.size: return self.addAtTail( val ) # 找到前驱节点 cur = self.dummy_head for i in range( index ): cur = cur.next node = ListNode( val ) node.next = cur.next cur.next = node self.size += 1 return self.dummy_head.next return None def deleteAtIndex(self, index: int) -> None: self.get( 1 ) if index >= 0 and index < self.size: # 需要注意尾节点的变化 cur = self.dummy_head for i in range( index ): cur = cur.next if index == self.size - 1: cur.next = None self.tail = cur else: cur.next = cur.next.next self.size -= 1 return self.dummy_head.next return None # Your MyLinkedList object will be instantiated and called as such: # obj = MyLinkedList() # param_1 = obj.get(index) # obj.addAtHead(val) # obj.addAtTail(val) # obj.addAtIndex(index,val) # obj.deleteAtIndex(index) ```