给定一个链表,如何确定其是否有循环?为了表示给定链表中的循环,使用整数pos来表示尾部连接到链表中的位置(0索引)。如果pos为-1,则链表中没有循环。举例如下。
输入:head=[3,2,0,-4],pos=1
输出:True
说明:链表中有一个循环,尾巴连接到第二个节点,如图8-3所示。
图8-3 循环链表
思路:利用两个指针,一快一慢,如果相遇就说明有循环。示例代码如下。
代码清单8-1 判断链表是否有循环 FJjEoaZ1y1BOc1d97yWYmmr5BGisU4ZWQFwIzYL8e4/ff0YxDfsqXRjwhHyKcCKu