Yahoo

  www.yahoo.com
  www.yahoo.com

Interview Question

Software Engineer Interview

Question about circular linked list, how to detect it and

  where to find the origin of the loop.
Answer

Interview Answer

2 Answers

0

Take two pointers. One increments by one node while the other by two. Iterate through the linked list, if at any time, both of them are equal, we have found a loop!

Sachin on Mar 15, 2013
0

I can think of two solutions to this problem. The first approach is to use a hash table to track the nodes that have already been traversed - should be O(n) time and O(2n) space.

The second approach is to use two pointers - one advancing two node at a time, one advancing one node at a time. Eventually the fast pointer will eventually fall on the same node as the slow pointer if a cycle exists in the list. This solution should be O(n) time and O(1) space.

Dan on Jul 18, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.