如何判断一个链表是否有环?如果有环,如何查找入环点?
有环链表:
无环链表:
两者的区别在于是否有尾节点和相交节点.
以是否有相交节点为突破口,这里介绍两种方法:
1....哈希表
对每个遍历过的节点进行记录,如果遍历到空节点,说明链表是无环链表;如果节点已记录过就说明链表是有环链表,这个节点就是链表的入环点....复杂度分析:
时间复杂度:O(N),只对链表做一次全遍历就可以确定;
空间复杂度:O(N),需要额外建立一个哈希表对链表节点进行存储.
2....根据这个思路,创建快慢两个指针,快指针,每次移动2个节点;慢指针,每次移动1个节点;如果两个指针有相交,则说明链表是有环链表,并且快指针的移动距离是慢指针的2倍.