1.题目

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改链表。

示例 1：

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

示例 2：

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

示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii

2.思路

（1）双指针
在解本题之前，需要先了解LeetCode_双指针_简单_141.环形链表这题，【141.环形链表】是要判断链表中是否存在环，有了该题的基础之后，再来看本题。解题的基本思路是：如果链表中有环，当快慢指针第一次相遇时，让其中任意一个指针指向头节点，然后让它们以相同的速度前进，当再次相遇时，所在的节点就是环的第一个节点。

3.代码实现（Java）

//思路1————双指针
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        //定义快慢指针
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                //当快慢指针相遇时，退出循环
                break;
            }
        }
        if (fast == null || fast.next == null) {
            //链表中无环，直接返回null
            return null;
        }       
        //上面的代码参考【LeetCode_双指针_简单_141.环形链表】
        
        //重新指向头结点
        slow = head;
        //快慢指针以相同的速度前进，相交点就是环的起点
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}