Solution to Finding Start of Loop in a Circular Singly Linked List

Question

The common solution that I find to this problem is to use 2 pointers that advanced through the linked list at different intervals (i.e. have p1 traverse one node at a time and p2 traverse two nodes at a time) until p1 and p2 are equals. Example: Finding loop in a singly linked-list

But why can't we just use a Set to see if there are duplicate nodes (Provided that our nodes don't have their default equals and hashCode overwritten).

Answer 1

Apply the next algorithm replacing the methods first and next by the proper one as in your language

slow=llist.first
fast=slow.next
while(true)
{
    if (slow==null || fast == null)
        return false// not circular
    if (fast==slow)
        return true//it is cirular
    fast=fast.next;if (fast!=null)fast=fast.next;
    slow=slow.next;    
}

here is a detailed example in C#:

    public class Node<T>
    {
        public Node<T> Next { get; set; }
        public T Value { get; set; }
    }
    class LinkedList<T>
    {
        public Node<T> First { get; set; }
        public Node<T> Last { get; set; }
        public void Add(T value)
        {
            Add(new Node<T> { Value = value });
        }
        public void Add(Node<T> node)
        {
            if (First == null)
            {
                First = node;
                Last = node;
            }
            else
            {
                Last.Next = node;
                Last = node;
            }
        }
    }
    static int IndexOfCiruclarity<T>(LinkedList<T> llist)
    {
        var slow = llist.First;
        var fast = slow.Next;
        int index = -1;
        while (true)
        {
            index++;
            if (slow == null || fast == null)
                return -1;
            if (fast == slow)
                return index;
            fast = fast.Next;
            if (fast != null) fast = fast.Next;
            else
                return -1;
            slow = slow.Next;
        }
    }
    void TestCircularity()
    {
        LinkedList<int> r = new LinkedList<int>();
        for (int i = 0; i < 10; i++)
            r.Add(i);
        r.Add(r.First);
        var ci = IndexOfCiruclarity(r);
        //ci = 9
    }