142. 环形链表 II

题目链接

一、哈希表

1、思想

类似

141.环形链表

的实现，只是将重合的节点打印出来。

2、代码实现

var detectCycle = function(head) {
    // 定义一个哈希表，用来存储节点
    var set = new Set();
    
    // 遍历链表，当链表里没有的时候，就插入到哈希表中。即将整个链表都放入哈希表中
    while(head){
        if(!(set.has(head))){
            set.add(head);           
        }else{
            // 如果哈希表里存在，就证明有环,返回下标
            return head; 
        }
        head = head.next;
    }
    return null;
};

二、快慢指针

1. 快指针和慢指针都指向头部，慢指针一次移动一个，快指针一次移动两个。
2. 当第一次相遇的时候，让其中一个指针指向head,然后以相同的步调进行移动。 第二次相遇的位置就是环的起点

var detectCycle = function(head) {
    let fast = slow = head;
    // 第一次相遇
    while (fast && fast.next) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast === slow) break;
    }
    // 判断fast是否为空
    if (!fast || !fast.next) {
        return null;
    }
    // 让slow重新指向head.这里需要注意循环条件，不能是上面的条件，因为第二次遍历的时候，指针有可能相遇，但是不是环的起点
    slow = head
    while (slow != fast) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
};