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?
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* p1 = head;
ListNode* p2 = head;
if(head==NULL)
return NULL;
while(p1&&p2&&p2->next)
{
p1 = p1->next;
p2 = p2->next->next;
if(p1==p2)
break;
}
if(p2==NULL||p2->next==NULL)
return NULL;
p1 = head;
while(p1!=p2)
{
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
};
网友评论