Expedia Amazon NVIDIA Knoa Software Apple Interview Question Software Engineer / Developers Interns
Pointers moving at different rates:
Pointer b moves 1 step ahead every time that pointer a moves 2 steps ahead. If there is a loop, eventually they will both enter it, and at some point because they are moving at different rates, they will be equal. If they are ever equal, you have a loop.
yes using two pointers works well .
other algo may be as follows:
reverse the linked list from .
while reversing if u start from first node.
after starting reversing if u find first node again .
there is loop in linked list.
reverse it again to find original list.
plz correct it if i m wrong, the cycle may not involve first node....
the algo by tyler seems correct without any memory overhead....
other approaches can be by using hashmap or by associating flag with each node to keep track if a node is already visited or not, although it involves memory overhead.
typedef struct node Node;
struct node {
Node * next;
};
bool is_cyclic(Node * list)
{
if(!list || !list->next) return false;
if(list->next == list) return true; // one element list pointed to himself
Node * first = list;
Node * second = list->next->next;
bool result = false;
while(second) {
if(first == second) {
result = true;
break;
}
first = first->next;
if(second->next == 0) { break; }
second = second->next->next;
}
return result;
}
<pre lang="java" line="1" title="CodeMonkey15826" class="run-this">// Here is the C# code.
public bool FindALoop()
{
if (Head == null)
{
return false;
}
Node slow = Head;
Node fast = Head;
while (slow.Next != null && fast.Next.Next != null)
{
slow = slow.Next;
fast = fast.Next.Next;
if (slow.Equals(fast))
{
//Found a loop
return true;
}
}
return false;
}</pre><pre title="CodeMonkey15826" input="yes">
</pre>
Consider a linked list which has a head (reference to the first node) and a current pointer. Traverse the loop and if at any point of time current-> next == head, voilla! you got a loop.
while( current.next != null ) {
if( current.next == head ) {
System.out.println("Loop detected!");
break;
}
current = current.next;
}
The above case covers the case where the loop is formed by connecting the last node to the first. In the case where the loop does not connect the end to the head, you could determine it as follows:
Consider two pointers, one traversing at twice the speed of the first. If there is a loop, there will be a point where the two pointers will meet, thus validating that a loop does exist!
I am writing only the function, rest is pretty much decoration !!!
int detectloop(struct node *list)
{
struct node *slow_p = list, *fast_p = list;
while(slow_p && fast_p &&
slow_p->next &&
fast_p->next &&
fast_p->next->next )
{
slow_p = slow_p->next;
fast_p = fast_p->next->next;
if (slow_p == fast_p)
{
printf("Found Loop");
return 1;
}
}
return 0;
}
Use 2 pointers to begin with. Move one pointer at double the speed of the other. if there is a loop, then they would be equal at one some point.
bool checkLoopPresent(Node *list){
Node *p1,*p2;
if (list == NULL) return false;
p1 = list;
p2 = list->nxt;
while((p1 != p2) && (p2 !=NULL) && (p2->nxt!=NULL)){
p1 = p1->nxt;
p2 = p2->nxt->nxt;
}
return p1==p2;
}
Nice solution by Neo above.
One other approach. We can use hash set to keep the distinct nodes.
private boolean checkLinkedListForLoop(Node first){
Set nodeSet = new HashSet();
if(first !=null){
Node ptr = first;
while(ptr !=null){
if(nodeSet.contains(ptr)){
return true;
}
else {
nodeSet.add(ptr);
}
ptr= ptr.getNext();
}
}
return false;
}
And Node class is ->
package linkedlist;
public class Node implements Cloneable{
private String value;
private Node next;
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Object clone(){
try {
Node clonnedNode = (Node)super.clone();
clonnedNode.next= (Node)next.clone();
return clonnedNode;
}
catch(CloneNotSupportedException cnse){
return null;
}
}
}
use two pointers:
bool HasLoop( Node *L )
{
Node *n1, *n2;
if( !L )
{
return false;
}
n1 = L;
n2 = n1->nxt;
while( n2 && n2->nxt )
{
if( n1==n2 || n1==n2->nxt )
{
return true;
}
n1 = n1->nxt;
n2 = n2->nxt->nxt;
}
return false;
}
correct it is a loop..bt representation should be....
___________
! !
n1->n2->n3->n4-!
becaz two node are same only when their address r same...
Maintain two pointers to traverse through the linked list, pointer1 & pointer2
do
pointer1 = pointer1->next;
pointer2->pointer2->next->next;
while(pointer2 && pointer2->next) //check for null condition, which if hit means no loop
the slower pointer1 will eventually catch up with faster pointer2 if there exists a loop.
The code for this problem would be:
boolean isCircular(node root)
{
if (root != null)
{
node slow=root;
node fast=root.next;
while ((fast!=null)&&(fast.next!=null))
{
if (fast==slow)
return true;
slow=slow.next;
fast=fast.next.next;
}
}
return false;
}
bool FindInList(stList* pList,stList* pList2)
{
bool bReturn = false;
stList* pList1 = pList;
if(pList1 == NULL || pList2 == NULL)
return bReturn;
while(pList1 != pList2)
{
if(pList1 == pList2)
{
bReturn = true;
break;
}
pList1 = pList1->pNList;
}
return bReturn;
}
bool FindLoop(stList* pList)
{
bool bReturn = false;
stList* pTemp = pList;
if(pTemp == NULL)
return bReturn;
while(pTemp != NULL)
{
if(FindInList(pList,pTemp))
{
bReturn = true;
break;
}
pTemp = pTemp->pNList;
}
return bReturn;
}
worst case O(n2) right but any body got O(n)solution for find the particular node where the loop starts
worst case O(n2) right but any body got O(n)solution for find the particular node where the loop starts
Am trying to use the length of list
and incrementing the counter to check if its equal to list size
is this correct. thnx
public boolean findLoop(LinkedList list)
{
Node cur = head;
counter = 0;
int len = list.size();
while(cur!=null)
{
cur=cur.next;
counter++;
if(counter == len)
return false;
}
return true;
}
This can be done using 3 pointers
1. Take a slow runner(Increase with one ) and a first runner(increment twice) approach to find the linklist is circular or not. If slow runner == fast runner then loop is circular.
2. Once you find the list is circular then loop the slow runner by one and the third pointer(which is now pointed to head) . Where they collide you can reach to the start of loop.
I guess it is good know about other algorithms besides Floyd's:
//Algorithm invented by Richard P. Brent and runs in O(n) time.
//Outline: initially rabbit and turtle starts
// off at same position however only rabbit moves by a step
// and checks if it meets the turtle. When it does
// not after a certain number of steps, the stationary
// turtle will be teleported to rabbit's position.
// The step counter as well as the limit of steps will
// will be reset. and rest of the actions just repeats.
//Algorithm starts here:
//assuming head would not point to head
//we start from 1st element, other wise
//we could have started from head as well
turtle = head ->next
rabbit = head ->next
steps_taken = 0
step_limit = 1 //1=2 power 0
forever:
if rabbit == end:
return 'No Loop Found'
end-if
rabbit = rabbit->next
steps_taken += 1
if rabbit == turtle:
return 'Loop found'
end-if
if steps_taken == step_limit:
steps_taken = 0
step_limit *= 2
// teleport the turtle
turtle = rabbit
end-if
end-forever
//Explanation: As we see that the turtle always sits at one position
// and rabbit moves to see if it meets the turtle. If it meets we
// have a cycle otherwise, let's just move the turtle directly to
// the position of rabbit instead of moving the turtle step by step
// as in Floyd's algorithm.
// We can see that such tele-porting of turtle would continue until the
// rabbit hits/enters the cycle. Once in side the circle it may happen
// that the rabbit still doesn't meet the turtle because the turtle is
// outside the loop (in fact haven't hit the loop yet). In such case
// turtle will be teleported again inside the loop skipping all nodes
// in between. Once both of them inside the loop, since turtle just
// sits there and rabbit makes moves, rabbit is bound to meet the turtle.
// If the step_limit is less than the loop size then even starting at inside
// the loop rabbit won't meet the turtle and the turtle will be teleported
// to a new location yet inside the loop. Since after each teleporting the
// step_limit increase (by two fold in this case), at some point of time,
// step_limit will be greater than loop length and then moving rabbit
// will move through the loop to meet the stationary turtle.
O(n) time complexity
Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.
// Best solution
function boolean hasLoop(Node startNode){ Node slowNode = Node fastNode = startNode; while (slowNode && fastNode) { if (slowNode == fastNode) return true; slowNode = slowNode.next(); fastNode = fastNode.next(); if (slowNode == fastNode) return true; fastNode = fastNode == null? null : fastNode.next(); } return false; }This solution is "Floyd's Cycle-Finding Algorithm" as published in "Non-deterministic Algorithms" by Robert W. Floyd in 1967. It is also called "The Tortoise and the Hare Algorithm".
- smashs March 31, 2012