Goldman Sachs Interview Question: How do you check if a Linked ... | Glassdoor

Goldman Sachs

## Interview Question

Summer Analyst Interview New York, NY

# How do you check if a Linked List has a recurring loop?

Tags:

0

I thought of using a hash table to store the values of each node, and adding values to the table as we iterate through the Linked List. This would only work if the values are unique. It was the not fastest or best either. With some hints, I came to a better solution of iterating through the Linked List twice - one that hops 1 node each time and the other hops 2 nodes each time. If the latter loop surpasses or reaches a node from the first, there exists a loop. There would be no loop of course when both reach the end of the Linked List.

Interview Candidate on Feb 16, 2013
0

There is a blog discussing this problem, as well as another problem to find the entry node in the loop.

Harry on Feb 17, 2013
0

There is a blog discussing this problem, as well as another problem to find the entry node in the loop. The link of the blog is:

http://codercareer.blogspot.com/2012/01/no-29-loop-in-list.html

Harry on Feb 17, 2013
1

/*
Jun Zheng, Rice Univ
C++, Xcode 4.5.2
Interview question of GS
Check if a linkedlist has circle, phead points to the start node
*/

while(pfast !=NULL && pfast->next !=NULL){
pfast=pfast->next->next;
pslow=pslow->next;
if(pfast==pslow) return true;
}
return false;
}

Jun Zheng on Feb 20, 2013