链表相关算法

发表于: 2017-04-10分类于:算法

如何判断链表中是否存在环

链表中有环是指,链表的结尾没有指向 null 而指向了链表中的某个节点。在遍历链表的时候,通常视 node->next == null 为链表的结束。如果链表中有环,在遍历链表的时候,如果依然使用上述判断结束的方法,那么将会陷入死循环。

判断链表中是否有环的方法很简单,使用快慢指针的方法,使用 slow 指针每次前进一个节点,而 fast 指针每次前进两个节点。

如果链表中没有环,由于 fast 指针前进的速度是 slow 的二倍,那么 fast 指针将率先到底链表的结尾(fast->next == null )。

如果链表中有环,那么可以想象 fastslow 指针都将在环上转圈,某个时刻 fastslow 指针将指向同一个节点。无论环上的节点数量是奇数还是偶数,

width=300px