Решение для поиска начала цикла в циклическом односвязном списке

Обычное решение, которое я нахожу для этой проблемы, состоит в том, чтобы использовать 2 указателя, которые продвигались по связанному списку с разными интервалами (т. е. чтобы p1 проходил по одному узлу за раз, а p2 — по два узла за раз) до тех пор, пока p1 и p2 не сравняются. Пример: Поиск цикла в односвязном списке

Но почему мы не можем просто использовать Set, чтобы увидеть, есть ли дубликаты узлов (при условии, что наши узлы не имеют своих равных по умолчанию и перезаписанных hashCode).


set hashset singly-linked-list
person James HS Johnson    schedule 20.05.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Примените следующий алгоритм, заменив методы first и next на правильный, как в вашем языке

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

вот подробный пример на С#:

    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
    }
person Aladdin    schedule 20.05.2015