题目
你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类：
MyLinkedList()初始化MyLinkedList对象。int get(int index)获取链表中下标为index的节点的值。如果下标无效，则返回-1。void addAtHead(int val)将一个值为val的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。void addAtTail(int val)将一个值为val的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)将一个值为val的节点插入到链表中下标为index的节点之前。如果index等于链表的长度，那么该节点会被追加到链表的末尾。如果index比长度更大，该节点将不会插入到链表中。void deleteAtIndex(int index)如果下标有效，则删除链表中下标为index的节点。
解法分析
使用带有虚拟头节点的写法更加简便
Python写法
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class MyLinkedList:
# 初始化头节点和链表的长度
def __init__(self):
self.head = ListNode()
self.size = 0
# 首先判断索引是否溢出，然后循环查找元素
def get(self, index: int) -> int:
print(self.size)
if index < 0 or index >= self.size:
return -1
# 使用了虚拟头节点，所以从头节点的下一个节点开始查找
current = self.head.next
for _ in range(index):
current = current.next
return current.val
# 在头节点增加一个节点首先让新节点指向头节点的下一个节点，头节点再指向新节点，最后更新链表长度
# 可以使用addAtIndex实现
def addAtHead(self, val: int) -> None:
new_node = ListNode(val)
new_node.next = self.head.next
self.head.next = new_node
self.size += 1
# 在链表尾部增加节点，首先遍历节点到尾节点，然后将尾节点指向新节点
# 可以使用addAtIndex实现
def addAtTail(self, val: int) -> None:
new_node = ListNode(val)
current = self.head
while current.next:
current = current.next
current.next = new_node
self.size += 1
# 首先判断索引是否溢出，若没有则循环寻找索引所在位置，将新节点指向当前节点的下一个节点，再将当前节点指向新节点
# 注意判断的边界！！当index等于size的时候，相当于在末尾增加节点
def addAtIndex(self, index: int, val: int) -> None:
if index < 0 or index > self.size:
return
new_node = ListNode(val)
current = self.head
for _ in range(index):
current = current.next
new_node.next = current.next
current.next = new_node
self.size += 1
# 首先判断索引是否溢出，若没有溢出则循环寻找索引位置，将当前节点的下一个节点指向下下个节点，链表长度减一
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index > self.size - 1:
return
current = self.head
for _ in range(index):
current = current.next
current.next = current.next.next
self.size -= 1
# 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)
