算法题心得 - 链表

上篇文章介绍了数组，哈希表，字符串相关的算法，这篇文章介绍另一个重要的数据结构，链表

链表特点

链表，和数组相比较的话，对于存储空间更加灵活，不像是数组，必须要求连续的空间，而且在数组中删除一个元素，就比较麻烦了，严格而言，删除数组中的一个元素，需要将后面的所有元素都向前移动。但是数组这种数据结构也有特别优秀的特点，就是查找的时间复杂度是O(1)。链表对存储空间很灵活，不要求连续，删除一个节点，只需要从整个链表中去掉就可以了。但是缺点就是查找的时间复杂度为O(n)。因此，究竟要用数组还是链表，要看项目的实际情况。

链表的节点可以理解为以下结构

struct _Node;
typedef struct _Node {
struct _Node* next_;
} Node;

可以发现，链表结构体中有一个指向下一个节点的next_，这也就是链表成链的关键。因此链表很容易考察对指针的理解，而指针，也就是处理链表相关问题的关键。

典型算法题

典型的算法题如面试题23：链表中环的入口节点

题目：如果一个链表中包含环，如何找出环的入口节点？

这是一道典型的链表题。上面分析过，解决链表类问题，最关键的就在于指针。对于这类问题，我们往往用两个指针，这两个指针可以从相同的节点出发，也可以从不同的节点出发，可以两指针的速度相同，也可以速度不同，巧妙的运用这些技巧，就可以解决一些复杂的问题。

比如解决这个问题，就需要类似的技巧。首先要对问题进行分解。对于复杂的问题，我们要想办法将其分解为简单的问题。比如这个问题，就可以做如下分解：如何判断链表中有环？如果有环的话，如何得到链表中环的个数？最后就是如何找到环的入口点？

判断链表成环

首先解决第一个问题，就是如何判断链表中有环。什么情况下有环呢？就是其中某一个节点，他的下一个节点又指向了前面的节点，如此一来，这个链表，就永远找不到结尾了。就好像是一个跑道，一直在绕着圈跑，却永远跑不到终点。有了这种启发，我们是不是可以判断链表的next有没有终止呢？如果从头开始遍历节点，如果某个节点的next_为nullptr，自然，就是没有成环的链表。如果找不到next_为nullptr的节点，则就是成环的链表。这是一个基本的思路，但是如果判断的条件是

while (node_->next_ != nullptr) {
node_ = node_->next_;
}
// 如果代码走到这里说明没有成环

这种判断有一个致命的错误，就是在成环的链表中，while的判断条件永远是true的，因此这个while循环是退出不了的。这当然是不可容忍的。如何让while循环可以停止呢？也就是如何在成环的条件下找到停止的条件呢？这就需要用到刚才提到过的双指针方法。其实思想非常简单，比如两个人赛跑，如果跑的快的那个人追上跑的慢的人，则跑道肯定成环。有了这种思想，我们定义两个指针，这两个指针都从链表的head开始跑，一个指针每次跑一个节点，另一个指针每次跑两个节点，这就是两个指针从相同的位置，但是速度不同的典型用法。如果一次跑两个节点的那个指针，碰到了node_->next_ == nullptr的情况，则说明链表不成环。如果一次跑两个节点的那个指针，追上了一次跑一个的那个指针，则说明链表成环。

确定链表环个数

下面我们来解决第二个问题，就是得到链表环中的个数。有了上一步的结果，如果成环的话，快指针会追上慢指针。追上的那个节点，肯定是环内的某个节点。我们可以从这个节点开始计数，让指针从这个节点开始出发，每次走一个节点，没走一个节点，计数增加。由于这个指针是环内的某个节点，因此，这个指针一定会回到他出发的地方。当他再次回到起始的节点时，我们统计的计数，就是环内节点的个数。

确定链表环起始节点

有了前面的结论，我们已经知道链表是否成环，如果成环的话，环内节点个数也清楚了。现在让我们找到环的起始节点。这里，我们还需要运用双指针的技巧，假设我们已经知道了环内的个数为k，我们可以定义两个指针，其中一个指针从头开始出发，另一个指针从第k个节点开始出发，两个指针每次往前走一个节点，当两个节点相遇的时候，就是环内的第一个节点。

小结

从上面的典型面试题可以看出，解决链表类问题，灵活的使用指针是关键，特别的，我们经常会使用双指针的技巧，两个指针可以从同一个节点出发，速度不同，也可以从不同的节点出发，速度相同等等。灵活的使用这些技巧，可以解决一些复杂的链表问题。特别的，对于任何复杂的问题，我们都要将其积极的拆分为简单的问题。这样才能化繁为简，一步一步的解决问题。