题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出 null

说明：不允许修改给定的链表

测试用例

• 输入：head = [3,2,0,-4], pos = 1
• 输出：返回索引为 1 的链表节点
• 解释：链表中有一个环，其尾部连接到第二个节点。

• 输入：head = [1,2], pos = 0
• 输出：返回索引为 0 的链表节点
• 解释：链表中有一个环，其尾部连接到第一个节点。

思路

快慢指针，如果有环的话，二者必相遇，用cur2记录相遇节点，然后令一个节点cur1从head出发，cur1和cur2同时出发，一次走一个节点，二者第一次相遇的地方，即是环的入口

代码实现

原地实现

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let fast = head;
    let slow = head;
    while(fast && fast.next){
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast){
            let cur1 = head;
            let cur2 = slow;
            while(cur1 != cur2){
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        }
    }
    return null;
};