Amazon Interview Question
SDE1sCountry: India
Interview Type: Written Test
You can use the following approach.
a.Take one pointer increment it by 2
b.Take another pointer increment it by 1.
c.If at any time first that is fast pointer reaches null then return false as loop does not exist.
d.If at any time second one that is the slow becomes equal to the first one then break.
e.Take the slow pointer to the start and then increment both by one till they become equal .That becomes the starting point of a loop in the linked list.
Solution in Java
import java.util.HashSet;
public class DetectLoops {
public static void main(String[] arg){
//We build a linked list from an array of Integer
Integer[] input = {0,1,2,3,4,5,6};
LinkedList<Integer> myList = new LinkedList<Integer>();
Node<Integer> current = myList.head = new Node<Integer>();
myList.head.value = input[0];
Node<Integer> savedForLoop = null;
for(int i=1; i<input.length; i++){
current.next = new Node<Integer>();
current.next.value = input[i];
if(i == 3)
savedForLoop = current;
current = current.next;
}
//Create the loop (6 -> 2)
current.next = savedForLoop;
System.out.println(myList);
}
}
class LinkedList<T>{
protected Node<T> head = null;
public String toString(){
HashSet<T> loop = hasLoop();
if(loop.size() > 0)
return "The linked list has a loop : " + loop;
Node<T> current = this.head;
StringBuilder buffer = new StringBuilder(current.value.toString());
while(current.next != null){
current = current.next;
buffer.append("->" + current.value);
}
return buffer.toString();
}
public HashSet<T> hasLoop(){
HashSet<T> loopValues = new HashSet<T>();
if(head == null || head.next == null)
return loopValues; //There are no loops!
//We declare two runners. One advances by one value at a time, the other one advances by two
Node<T> slow = head.next;
Node<T> fast = head.next.next;
Node<T> loopDetectedHere = null;
while(fast != null && fast.next != null){
if(fast.equals(slow)){
//There is a loop
loopDetectedHere = slow;
break;
}
fast = fast.next.next;
slow = slow.next;
}
if(loopDetectedHere != null){ //A loop was deteced
Node<T> current = loopDetectedHere.next;
while(!current.equals(loopDetectedHere)){
loopValues.add(current.value);
current = current.next;
}
}
return loopValues; //There are no loops. the fast runner reached the end of the linked list
}
}
class Node<T>{
protected T value = null;
protected Node<T> next = null;
public boolean equalsTo(Node<T> node){
return (node.value != null && this.value != null && node.value.equals(this.value)) || (node.value == null && this.value == null);
}
public String toString(){
return value.toString();
}
}
Simple.
First find whether there is loop or not (p= head->next, q=head->next->next).
If there is a loop, you will find a node where values of p and q will be same. Now print all
p->next till p->next ==p.
public boolean cycle(){
Node slow = head;
Node fast = head;
if(head == null)
return false;
boolean flag =false;
while((fast != null)){
if(fast.next == null)
return false;
fast = fast.next.next;
slow =slow.next;
if((fast == slow) || (slow.next == fast)){
if(slow.next == fast)
slow = slow.next;
flag = true;
break;
}
}
if(flag == true){
Node n = slow;
System.out.println("Cycle:");
do{
System.out.println(n.data);
n = n.next;
}while(n != slow);
return true;
}
else
return false;
}
Use the Floyd's cycle-finding algorithm (tortoise and the hare).
- whatevva' June 21, 2013