探索链表（下）

理解指针或引用的含义

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

警惕指针丢失和内存泄漏

插入结点时，一定要注意操作的顺序

删除链表结点时，也一定要记得手动释放内存空间（针对C语言）

利用哨兵简化实现难度

针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。这样代码实现起来就会很繁琐，不简洁。由此，引入 哨兵 的概念。这里说的哨兵也是解决“边界问题”的，不直接参与业务逻辑。

在任何时候，不管链表是不是空，head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。（相当于在原链表基础上再增加一个“头”节点，该节点不存储任何数据）

重点留意边界条件处理

经常用来检查链表代码是否正确的边界条件有这样几个：

• 如果链表为空时，代码是否能正常工作？
• 如果链表只包含一个结点时，代码是否能正常工作？
• 如果链表只包含两个结点时，代码是否能正常工作？
• 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

举例画图，辅助思考

多举例，多画图

多写多练，没有捷径

5 个常见的链表操作

• 单链表反转
• 链表中环的检测（快慢指针）
• 两个有序的链表合并
• 删除链表倒数第 n 个结点（快慢指针）
• 求链表的中间结点（快慢指针）

思考

还能够想到其他场景，利用哨兵可以大大地简化编码难度？