链表中存在环问题
3.1 判断链表是否有环
单链表中的环是指链表末尾的节点的 next 指针不为 NULL ，而是指向了链表中的某个节点，导致链表中出现了环形结构。
链表中有环示意图：
image.png
链表的末尾节点 8 指向了链表中的节点 3，导致链表中出现了环形结构。 对于链表是否是由有环的判断方法有哪些呢？
3.1.1 穷举比较法
3.1.1.1 解题思想
（1）遍历链表，记录已访问的节点。 （2）将当前节点与之前以及访问过的节点比较，若有相同节点则有环。 否则，不存在环。
这种穷举比较思想简单，但是效率过于低下，尤其是当链表节点数目较多，在进行比较时花费大量时间，时间复杂度大致在 O(n^2)。这种方法自然不是出题人的理想答案。如果笔试面试中使用这种方法，估计就要跪了，忘了这种方法吧。
3.1.2 哈希缓存法
既然在穷举遍历时，元素比较过程花费大量时间，那么有什么办法可以提高比较速度呢？
3.1.2.1 解题思想
（1）首先创建一个以节点 ID 为键的 HashSe t集合，用来存储曾经遍历过的节点。 （2）从头节点开始，依次遍历单链表的每一个节点。 （3）每遍历到一个新节点，就用新节点和 HashSet 集合当中存储的节点作比较，如果发现 HashSet 当中存在相同节点 ID，则说明链表有环，如果 HashSet 当中不存在相同的节点 ID，就把这个新节点 ID 存入 HashSet ，之后进入下一节点，继续重复刚才的操作。
假设从链表头节点到入环点的距离是 a ，链表的环长是 r 。而每一次 HashSet 查找元素的时间复杂度是 O(1), 所以总体的时间复杂度是 1 * ( a + r ) = a + r，可以简单理解为 O(n) 。而算法的空间复杂度还是 a + r - 1，可以简单地理解成 O(n) 。
3.1.3 快慢指针法
3.1.3.1 解题思想
（1）定义两个指针分别为 slow，fast，并且将指针均指向链表头节点。 （2）规定，slow 指针每次前进 1 个节点，fast 指针每次前进两个节点。 （3）当 slow 与 fast 相等，且二者均不为空，则链表存在环。
3.1.3.2 图解过程
无环过程：
image.png
image.png
image.png
通过图解过程可以看出，若表中不存在环形，fast 与 slow 指针只能在链表末尾相遇。
有环过程：
image.png
image.png
image.png
图解过程可以看出，若链表中存在环，则快慢指针必然能在环中相遇。这就好比在环形跑道中进行龟兔赛跑。由于兔子速度大于乌龟速度，则必然会出现兔子与乌龟再次相遇情况。因此，当出现快慢指针相等时，且二者不为NULL，则表明链表存在环。
3.1.3.3 代码实现
bool isExistLoop(ListNode* pHead) {
ListNode* fast;//慢指针，每次前进一个节点
ListNode* slow;//快指针，每次前进2个节点
slow = fast = pHead ; //两个指针均指向链表头节点
//当没有到达链表结尾，则继续前进
while (slow != NULL && fast -> next != NULL) {
slow = slow -> next ; //慢指针前进一个节点
fast = fast -> next -> next ; //快指针前进两个节点
if (slow == fast) //若两个指针相遇，且均不为NULL则存在环
return true ;
}
//到达末尾仍然没有相遇，则不存在环
return false ;
}
复制代码
3.2 定位环入口
在 3.1 节中，已经实现了链表中是否有环的判断方法。那么，当链表中存在环，如何确定环的入口节点呢？
3.2.1 解题思想
slow 指针每次前进一个节点，故 slow 与 fast 相遇时，slow 还没有遍历完整个链表。设 slow 走过节点数为 s，fast 走过节点数为 2s。设环入口点距离头节点为 a，slow 与 fast 首次相遇点距离入口点为 b，环的长度为 r。 则有： s = a + b; 2s = n * r + a + b; n 代表fast指针已经在环中循环的圈数。 则推出： s = n * r; 意味着slow指针走过的长度为环的长度整数倍。
若链表头节点到环的末尾节点度为 L，slow 与 fast 的相遇节点距离环入口节点为 X。 则有： a+X = s = n * r = (n - 1) * r + (L - a); a = (n - 1) * r + (L - a - X); 上述等式可以看出： 从 slow 与 fast 相遇点出发一个指针 p1，请进 (L - a - X) 步，则此指针到达入口节点。同时指针 p2 从头结点出发，前进 a 步。当 p1 与 p2 相遇时，此时 p1 与 p2 均指向入口节点。
例如图3.1所示链表： slow 走过节点 s = 6； fast 走过节点 2s = 12； 环入口节点据流头节点 a = 3； 相遇点距离头节点 X = 3； L = 8； r = 6； 可以得出 a = (n - 1) * r + (L - a - X)结果成立。
3.2.2 图解过程
image.png
image.png
3.2.3 代码实现
//找到环中的相遇节点
ListNode* getMeetingNode(ListNode* pHead) // 假设为带头节点的单链表
{
ListNode* fast;//慢指针，每次前进一个节点
ListNode* slow;//快指针，每次前进2个节点
slow = fast = pHead ; //两个指针均指向链表头节点
//当没有到达链表结尾，则继续前进
while (slow != NULL && fast -> next != NULL){
slow = slow -> next ; //慢指针前进一个节点
fast = fast -> next -> next ; //快指针前进两个节点
if (slow == fast) //若两个指针相遇，且均不为NULL则存在环
return slow;
}
//到达末尾仍然没有相遇，则不存在环
return NULL ;
}
//找出环的入口节点
ListNode* getEntryNodeOfLoop(ListNode* pHead){
ListNode* meetingNode = getMeetingNode(pHead); // 先找出环中的相遇节点
if (meetingNode == NULL)
return NULL;
ListNode* p1 = meetingNode;
ListNode* p2 = pHead;
while (p1 != p2) // p1和p2以相同的速度向前移动，当p2指向环的入口节点时，p1已经围绕着环走了n圈又回到了入口节点。
{
p1 = p1->next;
p2 = p2->next;
}
//返回入口节点
return p1;
}
复制代码
3.3 计算环长度
3.3.1 解题思想
在3.1中找到了 slow 与 fast 的相遇节点，令 solw 与 fast 指针从相遇节点出发，按照之前的前进规则，当 slow 与fast 再次相遇时，slow 走过的长度正好为环的长度。
3.3.2 图解过程
image.png
image.png
3.3.3 代码实现
int getLoopLength(ListNode* head){
ListNode* slow = head;
ListNode* fast = head;
while ( fast && fast->next ){
slow = slow->next;
fast = fast->next->next;
if ( slow == fast )//第一次相遇
break;
}
//slow与fast继续前进
slow = slow->next;
fast = fast->next->next;
int length = 1; //环长度
while ( fast != slow )//再次相遇
{
slow = slow->next;
fast = fast->next->next;
length ++; //累加
}
//当slow与fast再次相遇，得到环长度
return length;
}
你错过就亏了的十个 Java 面试题？你Get了吗？
工作一到五年的程序员朋友面对目前的技术无从下手，感到很迷茫，高清思维导图及相关视频资料获取方式关注+加群：714526711里面有阿里Java高级大牛直播讲解知识点，分享知识，课程内容都是各位老师多年工作经验的梳理和总结，带着大家全面、科学地建立自己的技术体系和技术认知！
网友评论