Linked List Cycle II

07/13/2016 Linked List Two Pointers

Question

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?

Solution

Result: Accepted Time: 4 ms

Here should be some explanations.

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode * fast = head, *slow = head;
    do
    {
        if(fast == NULL || fast->next == NULL)
            return NULL;
        fast = fast->next->next;
        slow = slow->next;
    }while(fast != slow);
    fast = head;
    while(fast != slow)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}

Complexity Analytics

  • Time Complexity:
  • Space Complexity: