链表（下）：如何轻松写出正确的链表代码？

2018-12-27 本文已影响3人红酥手黄藤酒丶

总结几个写链表代码的技巧。

一、理解指针或引用的含义

简单。。。。

对于插入操作而言，一定要注意操作顺序。

image

什么是哨兵呢？通俗意义上，哨兵解决的是国家的边界问题，这里的哨兵也是解决边界问题，不参与业务逻辑。

因为对链表的插入或删除操作，在一些情况下需要特殊处理：

if(head == null){
    head = new_node;
}

当要删除链表中的最后一个结点时（注意这里说的最后一个的含义：假设一个链表：1 2 3 4 删除其中三个结点后：1 2 3 留下的这个就是要表示的最后一个，所以如果头结点的后继指针为null，则表示该链表只有一个结点且是最后一个结点）

if (head->next == null) {
   //头结点指向了null，说明这个链表中一个结点都没有了，是一个空链表
   head = null;
}

这样我们发现，针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况做特殊处理，这样代码就会变繁琐，不简洁。

我们可以引入哨兵结点，在任何时候不管链表是不是空，head 指针都会一直指向这个哨兵结点。
我们也把这种有哨兵结点的链表叫带头链表。相反没有哨兵结点的链表就叫作不带头链表。

哨兵结点一直存在，但不存储数据，这样插入第一个结点和插入其他结点就可以使用相同代码了，同理，删除最后一个结点和删除其他结点也可以使用相同代码了。

image

这里利用哨兵简化变成难度的技巧，与此篇中第三个示例用到的技巧一样，可以看看了解一下，也是处理边界问题的方式，只不过正常写代码的时候我们不需要那么写，可读性太低了。

要实现没有 bug 的链表代码，一定要在编写的过程中以及编写完成之后，检查边界条件是否考虑全面，以及代码在边界条件下是否能正确运行。

满足上述四个问题，基本上这个链表代码就没什么问题了。

举例法和画图法，自己举个例子，在纸上画它的逻辑过程，这样非常有助于理解问题。

image

将下列五个常见的链表操作写熟练，妈妈再也不用担心面试官问我链表问题了。