题目:
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
分析:
检查链表是否有圈。
题目要求不能使用多余的空间。于是这里使用Floyd判圈算法,又称龟兔赛跑算法。算法逻辑如下:
- 指针hare初始化指向链表头结点,每次向后移动2个节点。
- 指针tortoise初始化指向链表头结点,每次向后移动1个节点。
- 如果hare最终指向尾节点或尾节点前一个节点(总结点数可能是奇数也可能是偶数),则该链表无圈。
- 如果hare和tortoise又指向了同一个节点,则该链表有圈。
通俗点的解释就是:龟兔赛跑,如果是一条直线,兔子永远会跑在前面;如果兔子发现又追上乌龟了,那么只能是兔子套了乌龟一圈。