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

Question

Общим решением, которое я нахожу для этой проблемы, является использование 2 указателей, которые продвигаются через связанный список с разными интервалами (т. Е. P1 пересекает один узел за раз и p2 пересекайте два узла за раз), пока p1 и p2 не равны. Пример: Finding loop in a singly linked-list

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

Answer 1

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

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

здесь подробный пример в 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 
    }