环链表是只链表中有环,例如下面:1->2->3->4->5->6->7->8->9->10->4,这样遍历的时候4->5->6->7->8->9->10->4就形成一个环路一直循环 。有环链表跟普通链表一样的,只不过构造数据的时候形成环路 。
例如下图:
环链表.png
思路:
用两个指针fast和slow指针(快慢指针),开始的时候指针都指向链表的Head节点,然后在每一步的操作中slow向前走一步:slow = slow.Next,
而fast就向前走两步 :fast = fast.Next.Next;
快指针fast由于比慢指针slow快,所以fast一定比slow先进入环
3.png
fast = fast.Next.Next;
slow = slow.Next;
也就是说,slow每次向前走一步,fast向前追了两步,因此每一步操作后fast到slow的距离缩短了1步,这样继续下去就会使得两者之间的距离逐渐减小,最后会在环中相遇;
复杂度:
时间复杂度:需要循环N次,所以时间复杂度未O(n);
空间复杂度:除了链表本身需要的内存空间外,并不需要其他的内存空间地址,所以空间复杂度为O(1);
完整代码(自测是OK的):
public bool CycleList()
{
//链表为空,或是单结点链表只有一个节点
if (Head == null || Head.Next == null)
{
return false;
}
Node<T> temp = Head;
Node<T> fast = temp;
Node<T> slow = temp;
while (fast.Next != null && fast.Next.Next != null)//当快指针与慢指针相遇时
{
fast = fast.Next.Next;
slow = slow.Next;
if (slow == fast)
{
return true;
}
}
return false;
}