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?
Subscribe to see which companies asked this question
查看是否有环，快慢两个指针一个移动一步，一个移动两步，是否相遇
查看环的起点，相遇后，将其中一个指针移到链表头，两个指针每次向后移动一步，相遇的点就是环的起点
证明可参考：http://www.cnblogs.com/wuyuegb2312/p/3183214.html
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;
}