数据结构与算法之美笔记——链表（下）

2019-04-14 本文已影响0人 Cloneable

摘要：

要正确写出操作链表的代码有一些技巧，例如明确指针或引用的含义、注意指针的丢失、使用哨兵简化实现难度、明确边界条件以及画图分析，当然多写多练也是必须的。

学习了链表的基础知识后要写出正确的链表操作代码并不容易，当然亲自动手写得不多也是原因之一，但在写出正确的链表操作代码上是有一些技巧的。

链表的结点之间依靠指针进行关联，有些语言中有指针的概念，而有的语言中是使用引用，但作用都是相似的，在链表中指针或者引用存储的都是结点的内存地址，通过内存地址可以找到结点。

在链表操作中，非常容易出现丢失指针的操作，比如在 p 结点后面插入 x 结点，代码有可能就会这样写

p.next = x;
x.next = p.next;

而正确的代码应该是

x.next = p.next;
p.next = x;

虽然只是两句代码颠倒了一下，但效果完全不同，第一段代码中 p 结点的后继指针已经指向 x，当 x 的后继指针指向 p 的后继指针时也就变成了指向自己，所以在书写正确的链表操作代码时特别要注意指针丢失的情况。

哨兵一般用来解决分界问题，例如在链表的插入操作中，一般结点都可以这样写

newNode.next = p.next;
p.next = newNode;

但向一个空链表插入结点时，便需要特别的操作

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

删除操作也会有类似的情况发生，删除一般结点时

p.next = p.next.next

当删除的链表只有一个结点时，也需要进行特别操作

if(head.next == null) {
  head = null;
}

当特殊情况出现时不仅代码上需要增加判断和操作，而且对特殊情况考虑不全面时写的代码会有 bug。我们可以利用哨兵的概念，给链表增加一个头结点，这个头结点不存储数据，只存储指针，这种链表称为带头链表，因为链表自身携带头结点，所以上面两段代码讨论的特殊情况也就不存在了，也就利用哨兵简化了实现难度。

其实不止是链表的操作代码，在代码实现正常的逻辑操作后，还需要考虑在边界情况下代码是否能正常处理，处理后的结果是否符合逻辑，链表操作常用边界条件有这样几个：

可以利用画图的方式将抽象的链表操作具体化，让自己更加专注思考其中的逻辑。

最后再多的技巧也需要多加练习，这章节写得较短，在文末附上链表反转和合并有序链表的算法练习，点击相应名称进行跳转。

文章中如有问题欢迎留言指正
数据结构与算法之美笔记系列将会做为我对王争老师此专栏的学习笔记，如想了解更多王争老师专栏的详情请到极客时间自行搜索。