链表（下）—— 6个技巧教你写出正确的链表代码

指针或引用存储的是对象的内存地址。将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针。

p->next=q 表示 p 结点中的 next 指针存储了 q 结点的内存地址。从左到右读就可以，p 的下一个结点就是 q。

拿单链表的插入举例。在结点 a 和相邻的结点 b 之间插入 x，假设当前指针 p 指向结点 a。

p->next = x;  // 将 p 的 next 指针指向 x 结点；
x-next = p -> next;  // 将 x 的结点的 next 指针指向 b 结点；
复制代码

很显然，上面的代码执行结果有问题。结点 x 最终指向自己，这样链表就断开了，造成内存泄漏。所以应该颠倒一下顺序。

在插入结点时，一定要注意操作的顺序，这样才不会丢失指针。删除结点时，一定记得手动释放内存，以免产生内存泄漏。

针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。比如判断是否为 null。

引入哨兵结点，不管链表是不是空，head 指针都会一直指向这个哨兵结点。把这种有哨兵结点的链表叫带头链表。相反。没有哨兵结点的链表就叫作不带头链表。

哨兵结点是不存储数据的。因为哨兵结点一直存在，所以插入第一个结点和插入其他结点，删除最后一个结点和删除其他结点，都可以使用相同的代码实现逻辑了。

常用来检查链表代码是否正确的边界条件：

实际上，不光是写链表代码，在写任何代码时，也千万不要只实现业务正常情况下的功能，一定要多想想，代码在运行的时候，可能会遇到哪些边界情况或者异常情况。遇到了应该如何应对，这样写出来的代码才够健壮！

你可以找一个具体的例子，把它画在纸上，释放一些脑容量，留更多的给逻辑思考，这样就会感觉到思路清晰很多。

精选了 5 个常见的链表操作，作为练习的题目。