Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:

Can you solve it without using extra space?

 

 to see which companies asked this question

 

查看是否有环，快慢两个指针一个移动一步，一个移动两步，是否相遇

查看环的起点，相遇后，将其中一个指针移到链表头，两个指针每次向后移动一步，相遇的点就是环的起点

证明可参考：

Linked List Cycle

bool hasCycle(ListNode *head) {    if (head == nullptr || head->next == nullptr)        return false;    ListNode *slow = head, *fast = head;    while (fast->next && fast->next->next)    {        fast = fast->next->next;        slow = slow->next;        if (fast == slow)            return true;    }    return false;}

Linked List Cycle II

ListNode *detectCycle(ListNode *head) {    if (head == nullptr || head->next == nullptr)        return nullptr;    ListNode *slow = head, *fast = head;    while (fast->next && fast->next->next)    {        fast = fast->next->next;        slow = slow->next;        if (fast == slow)        {            slow = head;            while (slow != fast)            {                slow = slow->next;                fast = fast->next;            }            return slow;        }    }    return nullptr;}