# 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;
    }
}
```

 


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://soumyajit4419.gitbook.io/ds-algo/linked-list/linked-list-cycle.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.