数据结构与算法-链表（下）
这几天有点忙，虽然也不知道忙的啥。昨天晚上和九点兄一块去外边放了放飞机，差点没冻死。这是放飞的视频，略微不清晰。
今天又看了一期专栏，接着上回，结合专栏总结一下写链表代码的技巧。
理解指针和引用的含义
大一上 C 语言课的时候，看见指针就赶紧躲一边，碰都不敢碰，觉得太难了，可能也是受别人的影响，很多人都说难，难的也难，不难的也难了。
现在，我理解的指针，就是用来存储变量的地址，这有啥好处呢。指针在有些时候减少了变量之间数据的拷贝，提高了代码的效率，也减轻了内存的负担。当然，这只是指针的一小部分优点。当然指针也有缺点，比如在链表操作中，很容易出现一种情况，就是指针指着指着，不知道指哪去了，这会导致指针丢失和内存泄漏。
像Java 、Python 中，没有指针的概念，只有引用，引用是什么呢？下面看一段 Python 代码。
a = [1,2,3,4]
b = a
b.append(5)
print (a)
运行结果会是 [1,2,3,4,5],打印 b 看一下，也是 [1,2,3,4,5]，这就是引用的作用。代码中，a 是列表(list)对象，a 和 b 引用的是同一个对象，所以在 Python 中，对于可变对象（列表、字典、可变集合等）的操作，改变其中一个，另外一个也会随之改变，这里边涉及到栈内存和堆内存的知识。
警惕指针丢失和内存泄漏
下面看一个例子，在 a 和 b 之间插入一个节点 x。
如果插入代码这样写：
1 p -> next = x;
2 x -> next = p -> next;
这样写显然是不对的，第 1 行代码的意思是，p 的 next 指针存储 x 节点的地址，第二行是 x 的 next 指针存储 p 的下一个节点的地址。这就相当于 x 节点指向了自己，正确的写法是把 1、2 行代码调换一下。
利用哨兵简化实现难度
实现一个新节点的插入操作逻辑是这样的:
New_node -> next = p -> next;
p -> next = New_node;
但是碰上在一个链表中插入一个节点，让其成为头节点，这个逻辑就不对了，而需要链表判空操作。
New_node -> = head ;
删除一个节点是这样的：
p -> next = p -> next ->next;
但是删除链表中的最后一个节点，逻辑就不对了,也需要一个判空操作。
if (p -> next == NULL) {
p = NULL;
}
引入哨兵节点后，可以让插入和删除操作，在这两种特殊情况下的逻辑，和普通链表节点的插入和删除是一样的。哨兵节点是一个数据域为空的节点，将哨兵节点放在表头或者表尾可以实现这个功能。
重点留意边界情况处理
需要主要考虑以下几种情况
- 如果链表为空时，代码是否能正常工作？
- 如果链表只包含一个一个结点时，代码是否能正常工作？
- 如果链表只包含两个结点时，代码是否能正常工作？
- 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？
练好这几个链表操作
- 单链表反转
- 链表中环的检测
- 两个有序的链表合并
- 删除链表倒数第 n 个结点
- 求链表的中间结点
小结
链表看起来不难，写起来麻烦，还需多练。
