• 题目
• 大致意思
• 解决方案
• 源代码

题目

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

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

大致意思

给你一个链表，判断是否里面存在一个圆环

解决方案

• 使用两个指针slow,fast。两个指针都从表头开始走，slow每次走一步，fast每次走两步，如果fast遇到null，则说明没有环，返回false；如果slow == fast，说明有环，并且此时fast超了slow一圈，返回true。
• 为什么有环的情况下二者一定会相遇呢？因为fast先进入环，在slow进入之后，如果把slow看作在前面，fast在后面每次循环都向slow靠近1，所以一定会相遇，而不会出现fast直接跳过slow的情况。

源代码

var hasCycle = function(head) {
  head = U.getList(head);
  var slow = head;
  var fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      return true;
    }
  }

  return false
};