判断链表有环（LeetCode 141）

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

示例：
输入[3,2,0,4]（链表结构如下图） 输出：true

解法1：打标签法（污链表法）

通过打标签 flag 来解决问题，原链表的所有结点都没有 flag，从头结点开始遍历链表，给遍历过的结点立一个 flag，直到遍历到一个有 flag 的结点，证明链表是有环的

const hasCycle = function(head){
  while(head){
    if(head.flag){ // 如果 flag 为 true，证明环存在
      return true
    }else{ // 否则立一个 flag 继续往下走
      head.flag = true
      head = head.next
    }
  }
  return false
}

解法2：快慢指针

快慢指针同时从 head 出发，快指针一次走两步，慢指针一次走一步，如果直到快指针走到头，两者还没相遇说明无环，反之有环

var hasCycle = function(head) {
  let fast = head
  let slow = head
  while(fast && fast.next){
    fast = fast.next.next 
    slow = slow.next 
    if(slow === fast){
      return true
    }
  }
  return false
}

定位环的起点（LeetCode 142）

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

示例：
输入：head = [3,2,0,-4]（如下图） 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个结点。

思路分析：
和判断是否有环一样采用打标签法，返回有flag的结点

const detectCycle = function(head){
  while(head){
    if(head.flag){
      return head
    }else{
      head.flag = true
      head = head.next
    }
  }
  return null
}