6

Possible Duplicates:
find whether a loop in a linked list without two pointers
How to determine if a linked list has a cycle using only two memory locations.
Best algorithm to test if a linked list has a cycle

During a preparation for a job interview, I encountered the following question:

How can you determine whether a linked list (of any type) contains a loop, using additional space complexity of O(1)? You cannot assume that the loop starts at the first node (and of course, the loop doesn't have to contain all nodes).

I couldn't find the answer, though I have the feeling it's quite simple...

Community
  • 1
  • 1
ET.
  • 1,899
  • 2
  • 18
  • 28
  • I missed this exact question on an interview myself. I was only able to give the O(*n*) memory & time solution. – Thanatos Jun 08 '10 at 22:25
  • 1
    I learned about this in a CS class, but I don't think it's a particularly good question since it's "only obvious if you already know". – Brendan Long Jun 08 '10 at 22:26
  • Many, many duplicates, e.g. [find whether a loop in a linked list without two pointers](http://stackoverflow.com/questions/2338683/find-whether-a-loop-in-a-linked-list-without-two-pointers) – Paul R Jun 08 '10 at 22:33
  • Danny posted a good answer below -- if you want some search terms to learn more about it, try "Floyd's cycle detection algorithm" or "tortoise and hare algorithm". – Jim Lewis Jun 08 '10 at 22:36

3 Answers3

11

Easy. Maintain two pointers into the list. At each step, advance one pointer by a single link, and advance the other by two links. Test to see if they point to the same element. If so, you have a loop. If not, repeat until you find a loop or you reach the end of the list.

dty
  • 18,795
  • 6
  • 56
  • 82
  • 11
    I found that this solution was only "easy" if you knew it. This is, in my opinion, quite clever thinking. – Thanatos Jun 08 '10 at 22:22
  • Interesting. Why bother advancing the other at all? – T.E.D. Jun 08 '10 at 22:39
  • Any link may be equal to any other link, so they must both move around the list to test every (reachable) combination. – Ether Jun 08 '10 at 22:54
  • 1
    @T.E.D: The first node of the list may not be part of the cycle. IFF a cycle exists, there will be some i such that X_i = X_2*i, and the tortoise and hare algorithm finds the smallest such i if it exists. – Jim Lewis Jun 08 '10 at 22:59
  • Ahhhh. Thank you. The name sounds familiar, but my CS algorithms class was more than 20 years ago. – T.E.D. Jun 09 '10 at 12:56
1

Probably the same technique as checking if a graph is a tree (trees don't get to have cycles), see this this question. It recommends either a topological sort or a depth first search.

Community
  • 1
  • 1
zdav
  • 2,752
  • 17
  • 15
-1

I had this exact problem in real live code last week.

All I did was kept a pointer (link) for the first element. Then as I iterated through the list, if I ever got that pointer again, I know there's a loop.

T.E.D.
  • 44,016
  • 10
  • 73
  • 134