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?
Talking to a friend, who suggested based on a reversing linked list can give way to detect a cycle. But then there was a problem of restoring to the original state.
If there is a cycle in a given linked list, after reversing, the last pointer will be again head pointer as traversal will come back to start again and change in rotation orientation. But then there are some edge cases we may have to handle such as what if cycle contains only one element or the list has only one element? These cases can be easily fixed by putting extra checks.
After careful checking, I see just reversing twice would restore the list back to the original state and in O(n) time without any space.
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 = #cycli nodes. You can take from here and see what are the possibilities and consequences. Comment here to see if there is an issue.
- 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;
}