Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
// in this context, we've already know that the list has cycle
// suppose there is a class Node
// public class Node<Item>{
// Item item;
// Node next;
// }
// import the Node class here;
public class DetectCycleStartInList{// I wish I could use a better name :)
public Node detect(Node head){
if (head == null) return null;
Node slowRunner = head; // move at rate 1
Node fastRunner = head; // move at rate 2
while(true){
fastRunner = fastRunner.next.next;
slowRunner = slowRunner.next;
if (slowRunner == fastRunner) break;
}
while(true){
slowRunner = slowRunner.next;
head = head.next;
if (slowRunner == head) break;
}
return slowRunner;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment