141. 环形链表

;(function () {
  /**
   * 141. 环形链表
   * 给你一个链表的头节点 head ，判断链表中是否有环。
   * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，
   * 评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
   * 注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
   *
   * 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
   *
   * 输入：head = [3,2,0,-4], pos = 1
   * 输出：true
   * 解释：链表中有一个环，其尾部连接到第二个节点。
   *
   * 输入：head = [1,2], pos = 0
   * 输出：true
   * 解释：链表中有一个环，其尾部连接到第一个节点。
   *
   * 输入：head = [1], pos = -1
   * 输出：false
   * 解释：链表中没有环。
   *
   * 进阶：你能用 O(1)（即，常量）内存解决此问题吗？
   *
   */
  /**
   * Definition for singly-linked list.
   * class ListNode {
   *     val: number
   *     next: ListNode | null
   *     constructor(val?: number, next?: ListNode | null) {
   *         this.val = (val===undefined ? 0 : val)
   *         this.next = (next===undefined ? null : next)
   *     }
   * }
   */
  class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
      this.val = val === undefined ? 0 : val
      this.next = next === undefined ? null : next
    }
  }
  function hasCycle(head: ListNode | null): boolean {
    // 方法一： 官方 -> 哈希表
    // let map = new Map();
    // while (head) {
    //     if (map.has(head)) return true; // 如果当前节点在map中存在就说明有环
    //     map.set(head, true); // 否则就加入map
    //     head = head.next; // 迭代节点
    // }
    // return false; // 循环完成发现没有重复节点，说明没环

    // 方法二： 官方 -> 快慢指针
    // 设置快慢指针
    // let slow = head;
    // let fast = head;
    // // 如果没有环，则快指针会抵达终点，否则继续移动双指针
    // while (slow && fast && fast.next) {
    //     slow = slow.next;
    //     fast = fast.next.next;
    //     // 快慢指针相遇，说明含有环
    //     if (slow == fast) {
    //         return true;
    //     }
    // }
    // return false;

    // 方法三： DIY
    // ?????
    return true

    // 方法四： 链表反转 - 再比较
    // todo

    // 其他： 天秀解法
    // 1. JSON.stringify(head) 秒杀法： 除非不报错，报错就是有环！！
    // try {
    //     JSON.stringify(head)
    // } catch{
    //     return true
    // }
    // return false

    // 2. 鸡贼法: 题目说了范围不超过100000，没超过size能发现空节点就是没有环， 超过了就是有环！！！
    // let i = 0, size = 100000
    // let node = head
    // while (++i <= size) {
    //     if(!node) return false
    //     node = node.next
    // }
    // return true;
  }
})()
141. 环形链表 ​

141. 环形链表
