Sunday, November 24, 2013

Leetcode Problem : Linked List Cycle II

Problem



Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?

Code

ListNode *detectCycle(ListNode *head) {
    // IMPORTANT: Please reset any member data you declared, as
    // the same Solution instance will be reused for each test case.
    ListNode *p1 = head;
    if(!p1)
        return 0;
    ListNode *p2 = p1;
    while(p1 && p2){
        p1 = p1->next;
        p2 = p2->next;
        if(p2)
            p2 = p2->next;
        if(p1 && p1 == p2)
         break;
    }
    if(p2 && p1){
        ListNode *p3 = head;
        while(p1 != p3){
            p1 = p1->next;
            p3 = p3->next;
        }
        return p3;
    }
    return 0;
}

No comments:

Post a Comment