Как дела? Да, есть этот алгоритм Флойда, но знаете, как сложно его объяснить. Да, да, это может быть несложно, если вы помните. Есть ли более простой способ обнаружить цикл?

Разговор с другом, который предложил на основе обратно связанного списка, может помочь обнаружить цикл. Но потом возникла проблема восстановления в исходное состояние.

Если в данном связанном списке есть цикл, после реверсирования последний указатель снова станет указателем головы, поскольку обход вернется к началу снова и изменит ориентацию вращения. Но тогда есть некоторые крайние случаи, которые нам, возможно, придется обрабатывать, например, что, если цикл содержит только один элемент или список имеет только один элемент? Эти случаи можно легко исправить, поставив дополнительные проверки.

После тщательной проверки я вижу, что простое переворачивание дважды вернет список в исходное состояние и за время O (n) без пробела.

Этот метод также полезен для печати циклических элементов, а также дает представление о пройденных элементах. 2x+y+1 — пройденные элементы, где x = #нециклические узлы и y = #циклические узлы. Вы можете взять отсюда и посмотреть, каковы возможности и последствия. Прокомментируйте здесь, чтобы узнать, есть ли проблема.

  1. Учитывая общее количество и связанный список, содержащий цикл, легко найти начальную позицию цикла, решив два уравнения.

x + y = n, n = общее количество;

2x+y+1 =m, m = итерации обратно связанного списка.

Решая их, легко найти начало цикла.

public boolean hasCycle(ListNode head) {
  if ( head == null || head.next == null) return false;
  if (head.next == head) return true;
  ListNode prev = null;
  ListNode curr = head;
  while(curr != null) {
   if(curr.next == curr) return true;
   ListNode temp = curr.next;
   curr.next = prev;
   prev = curr;
   curr = temp;
   System.out.print(prev.val+” “);
 }
 System.out.println(“ — — — First Traversal Done — — — -”);
 prev = null;
 curr = head;
 while(curr != null) {
  if(curr.next == curr) return true;
  ListNode temp = curr.next;
  curr.next = prev;
  prev = curr;
  curr = temp;
  System.out.println(prev.val+” “);
 }
 System.out.print(“ — — — Second Traversal Done — — — -”);
 prev = null;
 curr = head;
 while(curr != null) {
  if(curr.next == curr) return true;
  ListNode temp = curr.next;
  curr.next = prev;
  prev = curr;
  curr = temp;
  System.out.print(prev.val+” “);
 }
 System.out.println(“ — — — Third is Nothing but First Traversal Done — — — -”);
 return prev == head;
}