链表（下）
熟练掌握链表的六大技巧
- 理解指针或引用的含义
- 警惕指针丢失和内存泄漏
- 利用哨兵简化实现难度
- 重点留意边界条件处理
- 举例画图，辅助思考
- 多写多练，没有捷径
技巧一：理解指针或引用的含义
含义：将某个变量（对象）赋值给指针（引用），实际上就是就是将这个变量（对象）的地址赋值给指针（引用）。
以 C 语言来举例：
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。1 p->next=q 2 p->next=p->next->next
第一行代码表示，p 结点中的 next 指针存储了 q 结点的内存地址。
第二行代码表示，p 结点的 next 指针存储了 p 结点的下下一个结点的内存地址。
技巧二：警惕指针丢失和内存泄漏
指针在什么情况下会丢失呢？我们来看一张图片：
如图所示，假如我们希望在 b 节点和 c 结点之间插入 x 结点，假设当前指针指向结点 b，如果我们写出以下代码，就会发生指针丢失和内存泄漏。
1 p->next = x; // 将 p 的 next 指针指向 x 结点； 2 x->next = p->next; // 将 x 结点的 next 指针指向 c 结点
这里 p->next 指针在完成第一步操作之后，已经不再指向结点 c 了，而是指向结点 x。第 2 行代码相当于将 x 赋值给 x->next，自己指向自己。因此，整个链表也就断成了两半，从结点 c 往后的所有结点都无法访问到了。对于这段代码，我们只需要把两行代码的顺序调换一下就不会出错了。
对于有些语言来说，比如 C 语言，内存管理是由程序员负责的，如果没有手动释放结点对应的内存空间，就会产生内存泄露。所以，我们插入结点时，一定要注意操作的顺序，以免出现指针丢失，内存泄漏等问题。
同理，删除链表结点时，也一定要记得手动释放内存空间，否则，也会出现内存泄漏的问题。当然，对于像 Java 这种虚拟机自动管理内存的编程语言来说，就不需要考虑这么多了。
技巧三：利用哨兵简化实现难度
1.什么是“哨兵”？
- 链表中的“哨兵”结点是解决边界问题的，不参与业务逻辑。
- 如果我们引入“哨兵”结点，则不管链表是否为空，head 指针都会指向这个“哨兵”结点。
- 我们把这种有“哨兵”结点的链表称为带头链表，相反，没有“哨兵”结点的链表就称为不带头链表。
2.在不引入“哨兵”的时候
如果在p节点后插入一个结点，只需2行代码即可搞定：
1 new_node—>next = p—>next; 2 p—>next = new_node;
但若向空链表中插入第一个结点，则代码如下：
1 if(head == null){ 2 head = new_node; 3 }
如果要删除结点 p 的后继结点，只需1行代码即可搞定：
1 p—>next = p—>next—>next;
但若是删除链表的最后一个结点（链表中只剩下这个结点），则代码如下：
1 if(head—>next == null){ 2 head = null; 3 }
从上面的情况可以看出，针对链表的插入、删除操作，需要对插入第一个节点和删除最后一个节点的情况进行特殊处理。这样代码就会显得很繁琐，所以引入“哨兵”结点来解决这个问题。
3.引入“哨兵”的情况
“哨兵”结点不存储数据，无论链表是否为空，head指针都会指向它，作为链表的头结点始终存在。这样，插入第一个结点和插入其他结点，删除最后一个结点和删除其他结点都可以统一为相同的代码实现逻辑了。
4.“哨兵”最大的作用是什么？
简化边界条件的处理。
技巧四：重点留意边界条件处理
针对链表，检查代码是否正确的边界条件有以下四个：
- 如果链表为空时，代码是否能正常工作？
- 如果链表只包含一个结点时，代码是否能正常工作？
- 如果链表只包含两个结点时，代码是否能正常工作？
- 代码逻辑在处理头尾结点时是否能正常工作？
针对不同的场景，可能还有特定的边界条件，这个需要你自己去思考，但套路都是类似的，多加练习就懂了。
技巧五：举例画图，辅助思考
对于一些较为复杂的链表操作，指针一会儿指这，一会儿指哪，这种时候就很难靠大脑去分析了，可以使用举例法和画图法来解决。比如，假设你要往单链表中插入一个数据，举个例子，画出插入数据前后的链表变化，如图所示：
这样看起来就直观多了，此时大脑不需要记住那么多东西，也留了更多的空间给逻辑思考。
技巧六：多写多练，没有捷径
需要学会熟练使用的 5 个链表操作：
- 单链表反转
- 链表中环的检测
- 两个有序链表合并
- 删除链表倒数第 n 个结点
- 求链表的中间结点
内容小结
写链表代码是最考验逻辑思维能力的，所以，一定要自己写代码实现一下链表的各种操作，才有效果。
