题目

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：

  • 你是否可以使用 O(1) 空间解决此题？

    示例1：

    image.png

    示例2：

    image.png

    示例3：

    image.png

    提示

  • 链表中节点的数目范围在范围 [0, 10] 内

  • -10 <= Node.val <= 10
  • pos 的值为 -1 或者链表中的一个有效索引

    题解

    如何判断链表是否有环

    链表环路.gif
    动态图中的方法就是快慢指针，快指针一次动两格，慢指针一次动一各，一快一慢这就是快慢指针

    如何判断是否环

    使用快慢指针，快的指针总比慢指针快，当快指针走到null值时，说明并没有环，但是如果是环的话，他们必定会在环内相交。一旦相交就说明环啦

    找出开始环的节点

    链表环路-找环节点.gif
    如何找出开始环的节点，在快慢指针第一次相交后，将快指针恢复到初始位置，让你每次前进一格，与慢指针的速度一致，
    image.png
    你看从头节点到环形入口节点的路途与相遇节点到环形入口节点的路途是一样的
    相遇节点到环形入口节点 = 头节点到环形入口节点
    那我可以将快指针恢复到初始位置也就是头结点，让它与慢指针的的速度一致，再次相交的点就是开始环的入口节点

    代码

    方法一 快慢指针

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

/**

  • @param {ListNode} head
  • @return {ListNode} / var detectCycle = function(head) { let slow = head,fast = head; /**如果有相等说明有环 / do{
    1.  /**
    2.  *判断是否无环
    3.  * 当fast的值为null 或者fast.next的值为null 说明没有下一个值啦
    4.  */
    5.  if(!fast || !fast.next) return null;
    6.  fast =  fast.next.next;
    7.  slow = slow.next;
    } while(slow != fast) // 跳出循环说明有环 // 让fast回到开始位置，一格一格的走 // 再次与slow相遇的地方就是环的的节点 fast = head; while(fast != slow) {
    1.  fast =  fast.next;
    2.  slow = slow.next;
    } return fast;

};

  1. 改进版本
  2. ```javascript
  3. /**
  4.  * Definition for singly-linked list.
  5.  * function ListNode(val) {
  6.  *     this.val = val;
  7.  *     this.next = null;
  8.  * }
  9.  */
  11. /**
  12.  * @param {ListNode} head
  13.  * @return {ListNode}
  14.  */
  15. var detectCycle = function(head) {
  16.     if(head == null || head.next == null) return null;
  17.     let slow = head, fast = head;
  18.     while(fast != null && fast.next != null) {
  19.         fast = fast.next.next;
  20.         slow = slow.next;
  21.         if(fast == slow) {
  22.             fast = head;
  23.             while(fast != slow) {
  24.                 fast = fast.next;
  25.                 slow = slow.next;
  26.             }
  27.             return fast;
  28.         }
  29.     }
  30.     return null;
  31. };

方法二 哈希表

  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val) {
  4.  *     this.val = val;
  5.  *     this.next = null;
  6.  * }
  7.  */
  9. /**
  10.  * @param {ListNode} head
  11.  * @return {ListNode}
  12.  */
  13. var detectCycle = function(head) {
  14.     const set = new Set()
  15.     let slow = head;
  16.     while(slow != null && slow.next != null) {  
  17.         if(set.has(slow)) {
  18.             return slow;
  19.         } else {
  20.             set.add(slow);
  21.             slow = slow.next;
  22.         } 
  23.     }
  24.     return null;
  25. };

参考文章

https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/142-huan-xing-lian-biao-ii-jian-hua-gong-shi-jia-2/