数据结构与算法(5):链表应用

上一篇文章我们一起学习了一下链表的基础，接下来呢，我们就一起学习一下链表的应用。首先，我们知道想要写好链表代码不是一件统一的事情，特别是一些比较复杂的链表操作，比如链表反转、有序链表合并等等，写的时候特别容易出错。所以能写对的人少之又少！！！

无论链表多么的难写，只要我们肯花精力和时间，我们每个人都会学会的。下面我们一起来了解几个写链表代码的技巧。

技巧一：理解指针或引用的含义

事实上，看懂链表结构并不难，但是一旦把它和指针联系在一起，就会让人摸不到头脑。所以，要想写好链表代码，首先就要理解好指针。

在有些语言中有"指针"的概念，比如：C语言；有些语言就没有"指针"的概念，取而代之的是"引用"，比如：Java、Python等；实际上，它们的意思都是一样的，都是存储所指对象的内存地址。

下面呢我们就用C语言中的指针，来了解一下，如果使用Java语言就理解成引用就OK

对于指针的理解呢，我们只需要记住一句话就可以了：将某个变量赋给指针，实际上就是将这个变量的地址赋给指针了，或者反过来说就是，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

在代码的编写中，我们会看到这样的代码：p->next=q，指的就是p结点中的next指针存储了q结点的内存地址。
还有更复杂的就是：p->next=p->next->next，这个表示的是，p结点中的next指针存储了q结点的下下一个结点的内存地址。

技巧二：警惕指针丢失和内存泄漏

大家可能会感觉上面的过程中，指针指来指去，一会就不知道指到哪里了。所以，我们在写的时候，一定注意不要把指针弄丢了。
接下来我们用单链表的插入操作来演示分析一下：

image.png

如图所示，我们要在结点a和结点b之间插入一个结点x，假设当前指针p指向结点a。如果我们将代码写成下面这个样子，就会出现指针丢失和内存泄漏

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

这就是我们可能会犯的错误。p->next指针完成第一步之后，就不在指向b结点了，而是指向结点x。第二行代码相当于将x赋值给x->next，自己指向自己了，因此，整个链表就断成了两半，从b结点往后的链表就都无法访问了。

对于有些语言来讲，比如C语言，内存管理是由程序员负责的，如果没有手动释放结点对应的内存，就会产生内存泄漏。所以，在我们插入结点时，一定要做一操作顺序。一定要先将x的next指针指向b结点，然后再将a的next指针指向x结点。所以，上面的两行代码顺序调换一下就可以了。

同理，删除链表结点时，也一定要记得手动释放内存空间，否则，也会出现内存泄漏问题。当然，像Java这种虚拟机自动管理内存的编程语言来说，就不需要考虑这么多了。

首先，我们先回顾一下单链表的插入和删除操作。如果我们在结点p后面插入一个新的结点，只需要下面两行代码就可以搞定。

new_node->next = p->next;
p->next = new_node;

但是我们如果向一个空链表插入一个结点，刚刚的逻辑就不实用了。我们需要做特殊的处理，其中head表示链表的头结点。所以，我们一个空的单链表的插入操作，就不一样了。代码如下：

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

接下来我们看一下删除操作，如果我们删除p结点的后继结点，那没问题，一行代码就搞定了：

p->next = p->next->next;

但是，如果我们删除的是链表的最后一个结点，那么刚刚的删除代码就是不OK的了。跟插入类似，也需要做特殊处理，代码如下：

if (head->next == null) {
   head = null;
}

根据上面的一步一步分析，我们可以看出，针对链表的插入、删除操作，需要插入第一个结点或者删除最后一个结点的时候，需要特殊的处理。这样的代码繁琐、不简洁，然而也很容易考虑不周到，而引发问题。为了解决这种问题，就引出了第三种技巧，利用哨兵来实现。利用哨兵来解决我们的这种边界问题。

如何表示一个空链表？那么head=null就表示了链表中没有结点了。其中head表示头结点的指针，指向链表中的第一个结点。

如果我们引用哨兵结点，在任何时候，无论链表是不是空链表，head指针都会一直指向这个哨兵结点。我们也把这种带有哨兵结点的链表叫做带头链表。相反，不带哨兵结点的链表叫做不带头链表。
下图是一个带头链表的示意图，可以看出，哨兵结点是不存储数据的，因为哨兵结点一直存在，所以插入第一个结点和插入其他接结点，删除最后一个结点和删除其他结点，都可以统一为相同的代码实现逻辑了。

image.png

实际上，这种利用哨兵简化编程难度的技巧，在很多代码实现中都有用到，比如插入排序、归并排序、动态规划等(后面的文章会写这些内容)。为了更好的理解，可以看一下下面这两段代码，分析一下：
代码一：

// 在数组 a 中，查找 key，返回 key 所在的位置
// 其中，n 表示数组 a 的长度
int find(char* a, int n, char key) {
  // 边界条件处理，如果 a 为空，或者 n<=0，说明数组中没有数据，就不用 while 循环比较了
  if(a == null || n <= 0) {
    return -1;
  }
  
  int i = 0;
  // 这里有两个比较操作：i<n 和 a[i]==key.
  while (i < n) {
    if (a[i] == key) {
      return i;
    }
    ++i;
  }
 
  return -1;
}

代码二：

// 在数组 a 中，查找 key，返回 key 所在的位置
// 其中，n 表示数组 a 的长度
// 我举 2 个例子，你可以拿例子走一下代码
// a = {4, 2, 3, 5, 9, 6}  n=6 key = 7
// a = {4, 2, 3, 5, 9, 6}  n=6 key = 6
int find(char* a, int n, char key) {
  if(a == null || n <= 0) {
    return -1;
  }
  
  // 这里因为要将 a[n-1] 的值替换成 key，所以要特殊处理这个值
  if (a[n-1] == key) {
    return n-1;
  }
  
  // 把 a[n-1] 的值临时保存在变量 tmp 中，以便之后恢复。tmp=6。
  // 之所以这样做的目的是：希望 find() 代码不要改变 a 数组中的内容
  char tmp = a[n-1];
  // 把 key 的值放到 a[n-1] 中，此时 a = {4, 2, 3, 5, 9, 7}
  a[n-1] = key;
  
  int i = 0;
  // while 循环比起代码一，少了 i<n 这个比较操作
  while (a[i] != key) {
    ++i;
  }
  
  // 恢复 a[n-1] 原来的值, 此时 a= {4, 2, 3, 5, 9, 6}
  a[n-1] = tmp;
  
  if (i == n-1) {
    // 如果 i == n-1 说明，在 0...n-2 之间都没有 key，所以返回 -1
    return -1;
  } else {
    // 否则，返回 i，就是等于 key 值的元素的下标
    return i;
  }
}

对比上面两段代码，如果字符串a很长的时候，比如几万，几十万甚至上百万的时候，大家认为那种代码运行更快一些呢？答案是第二种。因为两段代码执行次数最多就是while循环那部分。第二段代码我们通过一个哨兵a[n-1]=key，成功的省掉了一个i<n的比较语句，不要小看这一条语句，如果执行几万或者几十万次，累积的时间都会很明显。

当然，在实际的编程中不要写第二段这样的代码，因为可读性太差。在大部分情况下，我们并不需要追求如此极致的性能。

技巧四：重点留意边界条件处理

在开发过程中，代码在一些边界或者异常情况下，最容易产生bug。链表也不例外。如果要实现没有bug的链表代码，一定要在编写的过程中或者编写完成后考虑一些边界问题是否考虑全面，以及代码在边界条件下是否能够正确运行。

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

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

当你写完链表代码的时候，通过上面几点检查之后，还能正常运行，那么基本上是没什么问题了。

当然，边界的检查条件也不止上面举例的几种，还有很多是根据业务情况来定的。需要自己思考。

实际上不止链表代码需要考虑边界问题，在写任何代码时都需要考虑各种情况下的边界以及一些特定的场景需求，这样考虑周全之后，代码才会更加健壮。

技巧五：举例画图、辅助思考

对于一些复杂的链表操作，比如但链表反转，指针一会指这，一会指那的，一会就被绕晕了。这时候我们就可以使用举例法或者是画图法。

我们可以通过在纸上画出来，然后释放一些脑容量进行逻辑分析，这样思路会更清晰一些。

技巧六：多写多练，没有捷径

如果上面的方法，都理解并且掌握了，但是写代码的时候还是会出现各种错误，也不用着急，因为这个是需要多练习的，熟能生巧嘛！！！

我们可以尝试着练习一下以下的几种常见的链表操作。这几种练熟了，以后就不会怕写链表代码了

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

总结：
上面呢，就是能够帮你写出正确的链表代码的六个技巧。我认为，写链表代码最考验逻辑思维能力。因为，链表代码导出都是指针的操作、边界的处理，一不留神就会产生bug。从这里就能看出一个人是否足够细心。要不然面试官为什么总喜欢让求职者手写代码呢。这些知识都是需要多写多练，才能够更好的掌握。

解析(Java代码实现)：
单链表反转
链表中环的检测
两个有序的链表合并
删除链表倒数第n个结点
求链表的中间结点