本文主要是介绍leetcode No142. Linked List Cycle II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Question：
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Algorithm：
首先fast每次走两步，slow每次走1步，如果fast走到NULL，说明没有环，如果fast和slow相遇，说明有环，假设fast和slow在Z相遇，因为fast每次比slow多走1步，所以fast走的长度是slow的两倍。即2(a+b)=a+b+c+b。得出a=c。
所以此时一个指针p1从X处走，一个指针p2从Z处走，相遇的地方就是环的起点。
Accepted Code：
/*** 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 || head->next==NULL)return NULL;ListNode* pfast=head;ListNode* pslow=head;int flag=false;while(pfast!=NULL&&pfast->next!=NULL){pfast=pfast->next->next;pslow=pslow->next;if(pslow==pfast){flag=true;break;}}if(flag==false) //no cyclereturn NULL;ListNode* first=head;ListNode* last=pfast;while(first!=last){first=first->next;last=last->next;}return first;}
};这篇关于leetcode No142. Linked List Cycle II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
