判断一个链接有没有环，很著名的算法是Floyd判圈算法，也叫龟兔算法。但是，原来还有一种算法，可以比Floyd更快一点，这种算法叫做Brent判圈算法。

算法思想

用2个指针rabbit和turtle从链表头出发。

  • rabbit先一步一步走，最多走2步，如果走到尽头，则无环，如果和turtle相遇，则有环，否则，本轮结束。
  • 这个时候，把turtle放到rabbit当前位置，rabbit继续一步一步走，但是最多走4步，如果走到尽头，则无环，如果和turtle相遇，则有环，否则，本轮结束。
  • 然后，把turtle放到rabbit当前位置，rabbit继续一步一步走，但是最多走8步，如果走到尽头，则无环，如果和turtle相遇，则有环，否则，本轮结束。
  • …

跟Floyd算法相比，假设一个5个元素的圆圈链表（尾部元素指回头部），Floyd算法需要走3 * 5 = 15步，而Brent算法只需要走2 + 4 + 5 + 2 = 13步。

代码实现

    bool hasCycleBrent(ListNode *head) {
      ListNode *p1 = head;
      ListNode *p2 = head;
      int steps = 0;
      int limit = 2;
      while (p1 != NULL && p2 != NULL) {
        p1 = p1->next;
        if (p1 == p2) {
          return true;
        }
        ++steps;
        if (steps == limit) {
          p2 = p1;
          steps = 0;
          limit *= 2;
        }
      }
      return false;
    }

参考