单项链表查找、相交或成环的几个算法

这篇文章介绍了单项链表上有关相交和成环的几个问题和算法。

你也可以参考有关单项链表的另外几篇文章：

单项链表实现的栈

反转单项链表的四种算法

判断两个单项链表是否相交

问题描述

给定两个单向链表，判断链表是否相交（有共同的节点）。

算法一

最直接的解法，就是对其中一个链表（链表一）进行遍历，在遍历到每一个节点时，都在另一个链表（链表二）中进行遍历，看是否有重复的节点，假设两个链表的长度分别是 n 和 m，那么最坏的渐进时间复杂度为 O (n * m)。

算法一的改进

凡是检索节点均可能进行改进。算法一中存在对链表二的多次扫描检索，可以采取以下思路进行简化：

• 以空间换时间：使用标记数组将链表二中存在的值进行标记，然后遍历链表一的时候，直接使用O (1) 的方法判断是否在于链表二中。但这要求链表二的内容取值范围较少或空间较大。简化后，时间复杂度变为 O(n + m)，但空间复杂度较高。
• 将链表二的内容排序，利用二分查找减少查找时间，将空间复杂度降低为 O(nlog[2](m))。

注意：这里所谓的“改进”有一个前提：节点的值不能重复。也就是说，重复节点值必须能够代表同一个节点。

算法二

算法二的思路基于以下两个原理：

• 两个单向链表相交后，必然无法再分开。这是很容易想到的，因为只有一个方向，一旦有相同的节点，那么后续的节点一定相同。
• 两个单项链表相交后，尾节点一定相同。基于第一个原理，容易想到第二个。

于是，我们给出这样的判断：两个链表相交，当且仅当两个链表的尾元素相同：

1. 假设两个链表相交，很容易证明两个链表的尾元素是相同的。
2. 逆反命题：两个链表的尾元素相同时，两个链表一定相交。（注意：相同的节点不仅仅要求值相同，而是“同一个”，也就是指针地址相同。）

算法思路如下：

1. 遍历链表一，找出尾节点指针。
2. 遍历链表二，找出尾节点指针。
3. 如果两个尾节点指针不为 nullptr 且相等，则两个链表相交。

查找相交的两个单向链表的第一个交点

这个问题是上面问题的扩展。通过观察两个相交链表的形状（Y字形），我们可以看到，如果从尾部看，从尾部到第一个交点的这部分节点是“对齐”的，而前面的长度不同。我们让前面也“右对齐”，这样比较是否相交节点的时候，只需要对比一次而不是遍历另一个节点。具体方法如下：

1. 找出两个链表的长度 len1 和 len2. 假设 len1 > len2.
2. 让长的链表先遍历 len1 - len2 次。
3. 两个链表一起遍历，每次都判断遍历到的是否是同一个节点。

如果单项链表是有环的，那又该如何找到交点呢？

• 如果单项链表一个有环，一个没环，那么他们不可能相交；（因为有环之后，如果相交，则另一个一定也就有环了）
• 如果检测两个都有环（见下面的算法），那么可以先找到环的起点，然后以此处为结束点，查找两个链表到此位置的长度 len1 和 len2，然后再用上述方法来解决。

判断单项链表是否有环

问题描述

给定一个单项链表，判断链表中是否存在环。

算法一

遍历单项链表，并对已经遍历到的节点进行标记。每次遍历的时候，从标记过的集合里查找，如果找到相同节点，说明链表有环。时间复杂度为 O (n^2)。当然，也可以通过改进查找算法减少时间复杂度，但不会降低到 O (n)。

算法二

使用两个指针同时遍历链表。假设这两个指针分别叫快指针 ptrFast 和慢指针 ptrSlow。

慢指针使用通常的方式遍历：每次遍历时有

ptrSlow = ptrSlow -> next;

快指针则以两倍的速度遍历：

ptrFast = ptrFast -> next;

设想：如果这个链表没有环，就如同一条直直的公路，快的一方永远不可能被慢的赶上。

但是，有环的时候，这种情况就不一样了：

因为快的指针进入环中并且不停循环，快指针和慢指针将很快相遇。

这种方法的时间复杂度为 O(n)。

查找链表元素

问题描述

查找链表中指定的元素：

1. 找到链表中倒数第 k 个元素。
2. 找到链表的中间元素。

算法一

我们先从直观上分析一下：要找到倒数第 k 个元素，必然要知道链表的长度，所以至少需要 O(n) 的时间。在不借助其他空间的情况下，此时我们无法反过来知道倒数第 k 个元素，因此必须重新遍历，所以至少需要遍历 2n - k 次。这种算法已经是很优秀的算法了，已经很难在不借助空间的情况下减少遍历了。

算法二

这个算法只是更“优雅”，其实没有变化：使用两个指针 ptrFirst 和 ptrSecond。

对于第一个问题：让两个指针有 k 步的遍历步距差值，这样当第一个指针指向最后时，第二个指针正好指向倒数第 k 个。其实遍历的次数和算法一相同。网上有一些文章误认为这种方式更高效，其实没有太本质的变化，只有常数的变化。

具体来说，就是先让 ptrFirst 遍历了 k 个节点后，两个指针再开始一起遍历节点。

同样道理，对于第二个问题：让 ptrFisrt 以两倍的速度遍历（参见本文上面的“快指针”和“慢指针”部分），当第一个指针遍历到最后一个节点的时候，第二个指针正好遍历到中点。

思考题：

1、如何找到链表 1/3 位置的节点？

2、如何找到单链表中环的起点和长度？（Tip：可以通过将单链表增加一维标记位，通过遍历将标记位 域填充；如果发现有节点已经被填充该域，则说明有环；此时，这个点就是环的起点。时间复杂度 O(n)，空间复杂度 O(n)。）