141.环形链表

[shengxinjing]

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

 

示例 1：

输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1 输出：false 解释：链表中没有环。

 

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

https://leetcode-cn.com/problems/linked-list-cycle/

[rongwei-alisa]

var hasCycle = function (head) {
    var node = head,
        nodeMap = new Map();
    while (node) {
        if (nodeMap.has(node)) {
            return true;
        }
        nodeMap.set(node, node);
        node = node.next;
    }

    return false;
};

[chenbingweb]

var hasCycle = function(head) {
        let fast = head;
		let slow = head;
		while (fast != null) {
			if (fast.next == null || fast.next.next == null)
				return false;
			fast = fast.next.next;
			slow = slow.next;
			if (fast == slow)
				return true;
		}
		return false;
};

[kaizige10]

想了很久也没想出来内存O(1)的解法，最终还是看了答案，用快慢指针：

/**
 * @param {ListNode} head
 * @return {boolean}
 */
// 使用快慢指针判断环的存在
var hasCycle = function(head) {
    if (head == null || head.next == null) return false
    
    let slow = head, fast = head.next
    while (slow != fast) {
        if (fast == null || fast.next == null) return false
        slow = slow.next
        fast = fast.next.next
    }
    return true
}

// @lc code=end
// 使用哈希表存储
var hasCycle_1 = function(head) {
    let map = new Map()
    let cur = head
    while(cur && !map.has(cur)) {
        map.set(cur, 0)
        cur = cur.next
    }
    return cur != null
};

快慢指针的结果：

[javin9]

var hasCycle = function (head) {
  // 0或者1
  if (!head || !head.next) {
    return false
  }
  let current = head
  while (current) {
    if (current['flag']) {
      return true
    }
    current['flag'] = true
    current = current.next
  }
  return false
};

打标记的方法

[chennailiang]

var hasCycle = function (head) {
  // 标记法
  // while (head && head.next) {
  //   if (head.flag) return true
  //   head.flag = true
  //   head = head.next
  // }
  // return false
  
  // 快慢指针解法
  if(!head || !head.next) return false
  let fast = head.next
  let slow = head
  while(fast != slow){
      if(!fast || !fast.next){
          return false
      }
      fast = fast.next.next
      slow = slow.next
  }
  return true
};