今天我学到了单链表和双链表的顺序表示，基本操作的实现，还了解了循环链表和双向循环链表。早上的重点是用例是UML统一建模语言的核心，接着是乒乓球横版的握持方法及上旋球发力动作要领及其训练。下午还有离散数学中序偶与笛卡尔积，集合关系及其表示。总之今天是充实的一天，也是非常耗费经历的一天。
实现单向链表，即每个节点仅存储本身的值和后继节点。除此之外，我们还需要一个哨兵（sentinel）节点作为头节点，和一个 size\textit{size}size 参数保存有效节点数。如下图所示。
初始化时，只需创建头节点 head\textit{head}head 和 size\textit{size}size 即可。
实现 get(index)\textit{get}(\textit{index})get(index) 时，先判断有效性，再通过循环来找到对应的节点的值。如下图所示。
实现 addAtIndex(index, val)\textit{addAtIndex}(\textit{index, val})addAtIndex(index, val) 时，如果 index\textit{index}index 是有效值，则需要找到原来下标为 index\textit{index}index 的节点的前驱节点 pred\textit{pred}pred，并创建新节点 to_add\textit{to\_add}to_add，将to_add\textit{to\_add}to_add 的后继节点设为 pred\textit{pred}pred 的后继节点，将 pred\textit{pred}pred 的后继节点更新为 to_add\textit{to\_add}to_add，这样就将 to_add\textit{to\_add}to_add 插入到了链表中。最后需要更新 size\textit{size}size。这样的操作对于 index=0\textit{index} = 0index=0 也成立，如以下两张图所示。
实现 addAtHead(val)\textit{addAtHead}(\textit{val})addAtHead(val) 和 addAtTail(val)\textit{addAtTail}(\textit{val})addAtTail(val) 时，可以借助 addAtIndex(index, val)\textit{addAtIndex}(\textit{index, val})addAtIndex(index, val) 来实现。
实现 deleteAtIndex(index)\textit{deleteAtIndex}(\textit{index})deleteAtIndex(index)，先判断参数有效性。然后找到下标为 index\textit{index}index 的节点的前驱节点 pred\textit{pred}pred，通过将 pred\textit{pred}pred 的后继节点更新为 pred\textit{pred}pred 的后继节点的后继节点，来达到删除节点的效果。同时也要更新 size\textit{size}size。
class ListNode: def __init__(self, val): self.val = val self.next = None class MyLinkedList: def __init__(self): self.size = 0 self.head = ListNode(0) def get(self, index: int) -> int: if index < 0 or index >= self.size: return -1 cur = self.head for _ in range(index + 1): cur = cur.next return cur.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 index = max(0, index) self.size += 1 pred = self.head for _ in range(index): pred = pred.next to_add = ListNode(val) to_add.next = pred.next pred.next = to_add def deleteAtIndex(self, index: int) -> None: if index < 0 or index >= self.size: return self.size -= 1 pred = self.head for _ in range(index): pred = pred.next pred.next = pred.next.next