9.Linked List Cycle

Problems related to Cycle Detection in Linked List

Determine if a Linked List has a cycle in it.

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

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

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