Goldman Sachs

  www.goldmansachs.com
  www.goldmansachs.com

Interview Question

Summer Analyst Interview New York, NY

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

Tags:
Answer

Interview Answer

4 Answers

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
     */
    bool ifCircular(node<T>* phead){
        node<T>* pfast=phead;
        node<T>* pslow=phead;

        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

Add Answers or Comments

To comment on this, Sign In or Sign Up.