Interview Question
Developer Program EngineersCountry: United States
Interview Type: Phone Interview
The idea is to have two references to the list and move them at different speeds. Move one forward by 1 node and the other by 2 nodes.
package com.dectectloops;
public class Node {
Node next;
public static void main(String[] args) {
// TODO Auto-generated method stub
}
boolean hasLoop(Node first) {
if(first == null) // list does not exist..so no loop either.
return false;
Node slow, fast; // create two references.
slow = fast = first; // make both refer to the start of the list.
while(true) {
slow = slow.next; // 1 hop.
if(fast.next != null)
fast = fast.next.next; // 2 hops.
else
return false; // next node null => no loop.
if(slow == null || fast == null) // if either hits null..no loop.
return false;
if(slow == fast) // if the two ever meet...we must have a loop.
return true;
}
}
}
By assigning removing any element in the loop you can remove a loop, if that's what you meant.
This is my code: but it is not working as expected: As in the loop is being detected but I am not able to remove the loop
- jsduder December 01, 2015