141.判断链表是否有环

环形链表

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

1. 利用JSON.stringfy()如果对象内有循环，则报错

var hasCycle = function(head) {
    try {
        JSON.stringify(head)
        return false
    } catch {
        return true
    }
};

2. 快指针

设置快慢两个指针，遍历单链表，快指针一次走两步，慢指针一次走一步，如果单链表中存在环，则快慢指针终会指向同一个节点，否则直到快指针指向 null 时，快慢指针都不可能相遇。空间复杂度为O(1)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    if(!head||head.next==null) return false
    var low=head,fast=head;
    while(fast.next&&fast.next.next){
        fast=fast.next.next;
        low=low.next;
        if(low==fast) return true
    }
    return false
};

3. 标志法 给每个已遍历过的节点加标志位，遍历链表，当出现下一个节点已经被标志时，则证明单链表有环

let hasCycle = function(head) {
    while(head) {
        if(head.flag) return true
        head.flag = true
        head = head.next
    }
    return false
};

时间复杂度：O(n) 空间复杂度O(n)

环形链表II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

题目说了不能修改给定链表所以不能使用标记法

• 在循环的过程中，快慢指针相遇，位置相同了，可以确定出相遇点
• 为了确定「入环点」，我们「人为制造」快慢指针在入环点相遇
• 让快指针从头节点出发，速度改为和慢指针一样，慢指针留在首次相遇点，同时出发
• 因为 D = S2D=S2 ，二者速度相同，所以会同时到达入环点

var detectCycle = function (head) {
  let slow = head;
  let fast = head;
  while (fast) {
    if (fast.next == null) { // fast.next走出链表了，说明无环
      return null;
    }
    slow = slow.next;        // 慢指针走一步
    fast = fast.next.next;   // 快指针走两步
    if (slow == fast) {      // 首次相遇
      fast = head;           // 让快指针回到头节点
      while (true) {         // 开启循环，让快慢指针相遇
        if (slow == fast) {  // 相遇，在入环处
          return slow;
        }
        slow = slow.next;
        fast = fast.next;    // 快慢指针都走一步
      }
    }
  }
  return null;
};