boolean hasCycle(Node linkedList) { if (linkedList == null) { return false; } Node n1, n2; n1 = linkedList; n2 = linkedList.getNext(); while (n1 != null && n2 != null) { if (n1.equals(n2)) { return true; } n1 = n1.getNext(); if (n2.getNext() != null) { n2 = n2.getNext().getNext(); } else { return false; } } return true; }
Algorithms and Data Structures Problems Solved. Coding Interviews for Google, Amazon, Microsoft, Apple, IBM... Improve your algorithmic problem solving skills. Java implementations.
google-code-prettify
Sunday, 2 December 2012
Cycle in LinkedList
There is an interesting technique how you can verify if there is a cycle in a LinkedList without using any additional data structure. All that is needed are two references (fast runner and slow runner) of the same type as the elements in the linked list. Here is the solution:
Labels:
cycle,
Java,
linked list
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment