快慢指针判断单向链表是否有环及找环入口

时间:2021-12-28 05:22:55

前言

关于快慢指针找环入口的这个问题,之前巴特跟我聊到过,印象比较深,今晚看学长在做的面试题,里面就出现了这个小知识。
发现有些东西不经意间就会用到,于是便出现此文。以后要努力做到善于总结,乐于总结。

概念

快慢指针,所谓的快慢,就是指指针每次移动的步长,通常使快指针每次向前移动两步,慢指针每次向前移动一步。

判断链表环及找环入口

操作

从链表头节点开始,快慢指针同时开始移动,快指针每次移动2,慢指针每次移动1,若快指针最终与慢指针相遇,则表示链表有环,否则,则为无环。
有环情况下,快慢指针相遇时,慢指针位置不变,将快指针置回表头,步长改为每次移1,快慢指针同时开始移动,再次相遇处即为环的入口。

原理

判断是否有环就不解释了,下面主要解释,为什么可以那样找环入口。

        ⬇️<-<-<-⬆️
⬇️ ⬆️
♦️->->->⬇️->->->⬆️
A B C

只是个简单图,就不专门做图了,凑合表示下吧。
♦️也就是A的位置是头节点,B表示环入口处,C表示快慢指针第一次相遇处。
在C处相遇时,设慢指针跑了N步,也就是从A开始N步后会到达C。
快指针比慢指针走的快一倍,也就是走了2*N步。那么慢指针从C处再跑N步还会回到C处。
既然都会回到C处,那么必然会在B点第一次相遇。
所以我们在入口处再设一指针(用之前快指针即可),与慢指针用1步长同时前进,第一次相遇处就是环入口处。

代码

/* 代码很简单 */
List* func(List* Head)
{
List* fast, slow;
fast = slow = Head;
while(fast != slow && fast != NULL)
{
slow = slow->next;
fast = fast->next;
if(fast != NULL)
fast = fast->next;
}
if(fast == NULL)
return true;
fast = Head;
while(fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return fast;
}

其他应用

譬如,给定一有序链表,求其中位数,因为不知道链表的具体长度,常规做法是先遍历一次,确定链表的长度,再遍历到中点,求出中位数。
但其实还有个更巧妙的法子,很方便的求出中位数,就是用快慢指针。
仍然是快指针步长为2,慢指针步长为1,当快指针到达链表尾部的时候,快指针就处于中点位置.(会牵扯到链表总数奇偶的情况,判断下即可,这里就不多赘述了)。