题目

题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。

思路

如何判断链表是否有环

快慢指针法

分别定义 fast 和 slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。
why?——

  1. fast指针一定先进入环中，如果fast 指针和slow指针相遇的话，一定是在环中相遇
  2. fast是走两步，slow是走一步，其实相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合

    如何找到环的路口

    具体分析看博客
    总而言之是，如果有环，那么slow和fast一定会在环内相遇点n，设环外部分为a，环的长度则为（n+b）
    这时slow指针走过的路程一定是a+n（一圈内），fast走过 a+n+m（n+b），而2slow =fast。得到数学关系
    所以此时再设两个指针，分别从头指针和相遇指针出发，一定会在入口汇合。

//定义一个节点在头结点处，定义一个节点在相遇的位置。两者同时移动，相遇的时候即入环节点的位置

  1. class Solution {
  2. public:
  3.     ListNode *detectCycle(ListNode *head) {
  4.         ListNode* fast =head;
  5.         ListNode* slow =head;
  7.         //fast指针走得快，如果无环则最终指向NULL
  8.         //因为一次走两步，所以有可能走到末尾/直接空
  9.         while(fast!=NULL && fast->next!=NULL){
  10.             slow =slow->next;
  11.             fast =fast->next->next;
  13.             if(slow ==fast){
  14.                 //相遇
  15.                 ListNode* a =head;
  16.                 ListNode* b =slow;
  18.                 while(a!=b){
  19.                     a =a->next;
  20.                     b =b->next;
  21.                 }
  22.                 return a;
  23.             }
  24.         }
  26.         return NULL;
  27.     }
  28. };

js 哈希表

  1.     let listSet =new Set()
  2.     let p =head
  3.     while(p){
  4.         if(listSet.has(p)){
  5.             return p
  6.         }
  7.         listSet.add(p)
  8.         p =p.next
  9.     }
  11.     return null

js双指针

var detectCycle = function(head) {
    if(!head) return null
    let fast=head,slow=head,cur=head
    // 验证fast和fast.next非空，考虑到fast要走两步
    while(fast&&fast.next){
        slow =slow.next
        fast =fast.next.next
        if(fast ===slow){
            while(cur!==slow){
                cur =cur.next
                slow =slow.next
            }
            return cur
        }
    }
    return null

};