How to know if linklint has a loop?

Question

Want to write the code in C to detect a loop in the link-list, please help.

Answer 1

boolean isLoopList (list *head)
{
    list *ptr1, *ptr2;
    ptr1 = ptr2 = head;

    while(ptr2 && ptr2->next)
    {
        ptr2 = ptr2->next->next;
        ptr1 = ptr1->next ;
        if (ptr1 == ptr2)
            return TRUE;
    }
    return FALSE;
}

Comments

Hi, This wont work for semi-circular i guess, will this work  ?

---

Did you try :)

Answer 2

Am just sharing idea, not code.

Make two pointers such that pointer1 traverse 1 by 1, pointer 2 traverse by 2.

List is not circular if pointer 2 meets NULL [have to make check for this].

List is circular if pointer2 meets any of first 2 element [have to make check for this also].

Such that for even number of nodes pointer 2 meets first element [Have to take backup of first 2 elements]

@Experts, Let me know if you have alternate approach.

Comments

Looks to be perfect solution, can you share the code also....