题目
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
输入： head = [3,2,0,-4], pos = 1 输出： 返回索引为 1 的链表节点 解释： 链表中有一个环，其尾部连接到第二个节点。
题解
第一种
我们这里采用的是快慢指针的方法，假设有两个指针：一个指针slow每次走一步，另一个指针fast每次走两步。如果链表中存在环，那么经过一些循环之后，快指针总会追上慢指针。在此期间，如果慢指针到达链表末尾，那么意味着链表无环。首先，如果链表为空或只有一个节点，就可以直接返回null。然后，设定fast和slow指针初始位置都为head。在while循环中，每次快指针fast向前移动两个位置，慢指针slow向前移动一个位置。如果存在环，最终快指针一定会追上慢指针并相遇。如果快指针和慢指针没有相遇，就代表链表中不存在环，直接返回null。接着，将慢指针slow重新指向head，然后再次进行循环，每次将快指针和慢指针都向前移动一个位置，直到它们相遇，相遇点就是链表中的环的连接点。最后返回该连接点。
var detectCycle = function(head) { if(!head || !head.next) return null; let fast = head; let slow = head; while(fast && fast.next){ fast = fast.next.next; slow = slow.next; if(fast == slow){ break; } } if(fast != slow){ return null; } slow = head; while(slow != fast){ fast = fast.next; slow = slow.next; } return slow; };
第二种
判断链表头结点是否为空或者链表只有一个结点，如果是则直接返回空。利用Set数据结构，创建一个保存链表结点的集合nodeSet，同时定义一个变量length用来保存nodeSet集合的大小。在while循环中，遍历链表，如果nodeSet不存在当前结点则把当前结点加入nodeSet集合中，同时将length设为nodeSet集合的大小，如果当前结点已经存在于nodeSet集合中，则说明链表有环，返回当前结点。如果遍历完整个链表都没有发现有环的结点，则返回null。
var detectCycle = function(head) { var result = null; if(head === null || head.next === null){ return result; } var nodeSet = new Set(); var length = 0; while(head !== null){ length = nodeSet.size; nodeSet.add(head); if(length === nodeSet.size){ result = head; break; } head = head.next; } return result; };
