本文主要是介绍Leetcode78: Linked List Cycle II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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?
大概思路就是：两个指针ptr1和ptr2，都从链表头开始走，ptr1每次走一步，ptr2每次走两步，等两个指针重合时，就说明有环，否则没有。如果有环的话，那么让ptr1指向链表头，ptr2不动，两个指针每次都走一步，当它们重合时，所指向的节点就是环开始的节点。
证明如下：我们知道ptr2每次都要比ptr1多走一步。
现在，假设ptr1需要m步第一次走到环的开始节点，那么ptr2应该走到了环的第m个位置（注意：这里是指环里的位置，ptr1在0处，ptr2在m处）。ptr2每次都比ptr1多走一步且它们都在环内，所以需要n-m步（n是环的大小），才能追上ptr1，达到重合。这个重合位置是[2*（n-m）+m-x*n]%n=n-m，这样我们就可以知道，重合的位置距离环开始节点有m步，head距离环开始节点也是m步。
/*** 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) {ListNode *fast, *slow;if(!head) return NULL;fast = head;slow = head;while(fast->next != NULL && fast->next->next != NULL){fast = fast->next->next;slow = slow->next;if(fast == slow){slow = head;while(fast != slow){fast = fast->next;slow = slow->next;}return fast;}}return NULL;}
};这篇关于Leetcode78: Linked List Cycle II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
