如何判断一个链表是否有环?如果有环,如何查找入环点?
有环链表:
无环链表:
两者的区别在于是否有尾节点和相交节点.
以是否有相交节点为突破口,这里介绍两种方法:
1....哈希表
对每个遍历过的节点进行记录,如果遍历到空节点,说明链表是无环链表;如果节点已记录过就说明链表是有环链表,这个节点就是链表的入环点....根据这个思路,创建快慢两个指针,快指针,每次移动2个节点;慢指针,每次移动1个节点;如果两个指针有相交,则说明链表是有环链表,并且快指针的移动距离是慢指针的2倍....快慢指针的移动轨迹参考下图,偏移4次的慢指针和偏移8次的快指针在节点5处相遇,链表是有环链表.
那入环点怎么判断呢?
我们再用平面几何的形式看下快慢指针的移动轨迹.