# 9.Linked List Cycle

## Determine if a Linked List has a cycle in it.

```cpp
bool detectCycle()
{
    bool res = false;
    if (head == NULL)
    {
        return false;
    }

    node *p = head;
    node *q = head;
    while (p->next != NULL && p->next->next != NULL)
    {
        q = q->next;
        p = p->next->next;
        if (q == p)
        {
            res = true;
            break;
        }
    }

    return res;
}
```

This algorithm is based on **Floyd’s Cycle-Finding Algorithm.** \
**Time complexity O(n) and Space Complexity O(1).**

This can also be solved using hash tables but we require an extra space of O(n). 

## Determine the node where the cycle begins

```cpp
node *getCycleBegin()
{
    if (detectCycle())
    {
        node *p = head;
        node *q = head;

        while (p->next != NULL && p->next->next != NULL)
        {
            q = q->next;
            p = p->next->next;
            if (p == q)
            {
                break;
            }
        }

        q = head;
        while (p != NULL)
        {
            if (q == p)
            {
                return p;
                break;
            }
            q = q->next;
            p = p->next;
        }
    }
}
```

This solution also includes the same cycle finding approach. 

* First, find the position where the two pointers meet.
*  Then we move one pointer to the head
* Iterate each pointer by one step.

## Determine the length of  the cycle

```cpp
int getCycleLen()
{
    node *p = head;
    node *q = head;
    node *temp = NULL;
    if (detectCycle())
    {
        while (p->next != NULL && p->next->next != NULL)
        {
            q = q->next;
            p = p->next->next;
            if (p == q)
            {
                temp = p;
                break;
            }
        }
        p = p->next;
        int s = 0;
        while (p != temp)
        {
            p = p->next;
            s = s + 1;
        }
        return s;
    }
}
```