Python程序 检测链表中的循环
当链表中的任何节点都不指向NULL时,就被称为链表中有一个循环。最后一个节点将指向链表中的一个以前的节点,从而创建循环。具有循环的链表将没有结束。
在下面的示例中,最后一个节点(节点5)没有指向NULL。相反,它指向节点3并建立了一个循环。因此,上面的链表没有结束。
算法 – 采用两个指针:快指针和慢指针
- 两个指针最初都指向链表的HEAD。
-
慢指针将始终增加1,快指针将始终增加2。
-
在任何时候,如果快指针和慢指针都指向同一节点,那么就称链表中有一个循环。
考虑下面的链表示例,其中最后一个节点指向第二个节点 −
示例
慢指针和快指针都指向同一节点。因此,可以得出结论:给定的链表包含一个循环。
输出
链表中检测到了循环。