1. 题目描述

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

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

在这里插入图片描述

2. 题解思路与算法

我们使用快慢指针。它们起始都位于链表的头部。随后，慢指针每次向后移动一个位置，而快指针向后移动两个位置。如果链表中存在环，则快指针最终将再次与慢指针在环中相遇。在判断有环的基础上。可以将链表分为三部分：从起点到?环点的距离a，从?环点到双指针相遇点的距离b，从相遇点到?环点的另?条路线c。

在这里插入图片描述

快指针的速度是慢指针的两倍，且慢指针?过的路径为 $a + b$ ，快指针?过的路径为 $a + b + n (b + c)$ 。可得到 $2 (a + b) = a + b + n (b + c)$ ，解得 $a = (n ? 1) (b + c) + c$ ，可得 $a = c$ 。

因此，只要找到指针相遇点后，在起点再定义?个标志指针，让其和慢指针?起移动，当
两个指针相遇的时候，那么指针所在的位置就是?环点。

3. 代码

1. C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head ==NULL) return NULL;
        ListNode *p = head,*q = head;
        while(q && q->next){
            p = p->next;
            q = q->next->next;
            if(p == q){
                q = head;
                while(q != p){
                    q = q->next;
                    p = p->next;
                }
                return p;
            }
        }
        return NULL;
    }
};

2. Java

/**
 * 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) {
        if(head ==null) return null;
        ListNode p = head,q = head;
        while(q != null && q.next != null){
            p = p.next;
            q = q.next.next;
            if(p == q){
                q = head;
                while(q != p){
                    q = q.next;
                    p = p.next;
                }
                return p;
            }
        }
        return null;
        
    }
}