LeetCode #141 Linked List Cycle

题目:

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

 

分析:

检查链表是否有圈。

题目要求不能使用多余的空间。于是这里使用Floyd判圈算法,又称龟兔赛跑算法。算法逻辑如下:

  1. 指针hare初始化指向链表头结点,每次向后移动2个节点
  2. 指针tortoise初始化指向链表头结点,每次向后移动1个节点
  3. 如果hare最终指向尾节点或尾节点前一个节点(总结点数可能是奇数也可能是偶数),则该链表无圈。
  4. 如果hare和tortoise又指向了同一个节点,则该链表有圈。

通俗点的解释就是:龟兔赛跑,如果是一条直线,兔子永远会跑在前面;如果兔子发现又追上乌龟了,那么只能是兔子套了乌龟一圈。

Continue reading LeetCode #141 Linked List Cycle