Detect loop in a linked list.

How do you do? Yeah, there is this Floyd’s algorithm, but do you know how complex it is to explain. Yes, yes, It may not be complex if you remember. Is there a more simple way to detect a cycle?

This method is also useful to print cyclic elements and also provides insight into traversed elements. 2x+y+1 is the traversed elements where x = #non-cyclic nodes and y = #cyclic nodes. You can take from here and see what are the possibilities and consequences. Comment here to see if there is an issue.

1. Given the total count and a linked list that contains a loop, it is easy to find the starting position of loop by solving two equations.

x + y = n, n = total count;

2x+y+1 =m, m = reverse linked list iterations.

By solving them it is easy to find the starting of a loop.

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