一、题目
二、思路
常规题，注意边界。
哨兵节点在树和链表中被广泛用作伪头、伪尾等，通常不保留任何数据。通常使用伪头来简化插入和删除。所以下面也用了伪头结点，所以注意题目中找第index个结点，还是从0号节点开始计算的，这里注意题目说的“假设链表中所有节点都是0-index的”，这里的0并非包括伪头节点。。就是说伪头节点的index并非是0，尤其注意这种边界问题。
如下图的栗子：
题目的增加和删除节点、获得index位置的节点，都是常规操作，另外可以先写addAtIndex函数，因为这样addAtHead和addAtTail都能直接使用这个addAtIndex函数了，做到代码复用。
三、代码
3.1 Python版本
class ListNode: def __init__(self, x): self.val = x self.next = None class MyLinkedList: def __init__(self): self.size = 0 self.head = ListNode(0) def get(self, index: int) -> int: if index >= self.size or index < 0: return -1 target = self.head for i in range(index + 1): target = target.next return target.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 > self.size: return if index < 0: index = 0 # 可以add了,计数加1 self.size += 1 # 找到目标index节点的前一个节点 pre = self.head for i in range(index):# 到第index-1 pre = pre.next node = ListNode(val) # 插入值为val的节点 node.next = pre.next pre.next = node def deleteAtIndex(self, index: int) -> None: if index < 0 or index >= self.size: return self.size -= 1 # 找到目标index节点的前一个节点 pre = self.head for i in range(index):# 到第index-1 pre = pre.next pre.next = pre.next.next # 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)
