142. 环形链表 II

1. 题目描述

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

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

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。

进阶：你是否可以不用额外空间解决此题？

3. 解题思路

这个和之前的141题原理一样，都是设置一个flag，只是返回值不一样，最后指向的是有flag 的节点，所以直接返回head即可。

上述方法需要开辟O(n)的储存空间来储存标记信息，可以尝试用快慢指针来解决这个问题：

我们设置两个指针，快指针每次走两个节点，慢指针每次走一个节点，如果存在环，那么两个指针一定相遇。等快慢指针相遇之后，我们在用另一个指针，去寻找他们相遇的位置就可以了。

4. 代码实现

第一种方法：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    while(head){
        if(head.flag){
            return head
        }else{
            head.flag = true
            head = head.next
        }
    }
    return null
};

第二种方法：

/**
 * 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
    let cur = head
    while(fast && fast.next && fast.next.next){
        slow = slow.next
        fast = fast.next.next
        if(fast == slow){
            while(cur!=slow){
                cur = cur.next
                slow = slow.next
            }
            return slow
        }
    }
    return null
};

4. 提交结果

第一种方法：

第二种方法：