9.14日

　　今天我学到了单链表和双链表的顺序表示，基本操作的实现，还了解了循环链表和双向循环链表。早上的重点是用例是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