LinkedList

链表的结构还是比较直观的，就像一条锁链，换换相扣。程序中它通过指针将零散的内存块地址串联起来，无须顺序存储；而指针即指向存储对象的内存地址的变量。

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向这个变量，通过内存地址可以找到这个变量值。

链表节点的结构：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

如图所示，一个节点记录两部分内容：

一般而言，第一个节点称作头节点，最后一个节点称作尾节点；头节点一般作为链表的起始标记，便于便利链表；尾节点的指针则是指向None,即空地址。

由于链表的特性，插入删除操作只需要找到对应节点直接插入即可，所以时间复杂度是O（1）；下面通过例子演示下插入操作：

如图，将在 23节点和12节点间插入14节点：

x.next = cur.next;  // 将 x 的结点的 next 指针指向下一结点；
cur.next = x;  // 将 cur 的 next 指针指向 x 结点；

实现插入、删除的过程需要注意赋值操作顺序。

我在做题的过程中，经常会想当然的先将当前节点和下一节点的连结断开，即cur.next指针指向x节点。再去关联x的后继节点。

若是像上面这样，将两句调换顺序则会指针丢失，导致断链。

上面提到头节点和尾节点有着不同的特性，因而在实现插入、删除操作的时候，需要格外进行处理，这样代码实现会繁琐许多。

这里将引入哨兵节点的概念，哨兵就像标识牌一样作为一个标志，如链表结构图中的head节点，该节点不直接参与业务，只是标记位置。

head节点一般不存储数据；当其作为一个标志位存在时，插入第一个节点和删除最后一个节点都可以复用同一代码逻辑。

代码实现过程中，总会碰到一些边界或是极端情况，这时候没有写边界条件，迎来的往往是雪崩。

之前做题就遇到过，由于未判定尾节点的情况，导致断链。做题的时候，最好列一下check list：

上面只是笼统的举例，具体还是得看题，想想极端情况下代码是否能运行；最好画下图解，方便记忆。