how do you remove a cycle in a single linked list?

Question

I am not sure how would I find the start of the cycle without using O(N) memory and flags

Answer 1

Traverse, and when you hit a node you've already visited, that's where the cycle comes back.

Answer 2

Either maintain a list of nodes visited to date and compare each node to the list as you come to it (slow, but requires no infrastructure), or "color" each node, and check if the next node is "colored" already (requires you to have a "color" flag installed in each node).

Or use 1800 INFORMATIONS's suggestion to get a node in the cycle. Use that to find a full list of the cycle, then retraverse the full list again (comparing with the cycle list as you go) to find the first node in the cycle.

Answer 3

There is a very nice algorithm that uses constant space, O(n) runtime and only two pointers. You traverse the list from the head with the first pointer, and at double speed with the second pointer. At each step compare the pointers, if they are ever equal, you have found the loop.

Answer 4

• Find a node inside the cycle (see 1800 INFORMATION's answer for details). Let's call this node C
• Find the length of the cycle by advancing a pointer from C until it reaches C again. The length of the cycle is the number of steps it took. Let's call this length L
• Create a pointer that is L steps forward from the starting point, and another that points to the start. Now advance them both one step at a time until they meet. This will be the entry point to the cycle.

O(N) time, O(1) memory.

btw, what do you need this for?

Answer 5

I think yairchu's answer using 1800's find method is the best solution - one of those solutions that made me smile to read it ;-)

But I will go ahead and post what I was thinking about, which only uses 4 extra pointers and a boolean.

Let's call the nodes a->b->c->...

If you start at a and go through the list flipping the pointers back the other way (need two of the extra pointers to help with this) and get all the way to an end that is not a, you of course have no loop. Woo woo! You can come back re-flipping the pointers and you're done.

But if you have a loop, what will happen is that you will make it all the way back to a, and the pointers will be left such that, the next time out and back, you will traverse the loop in the opposite direction. (You toggle the boolean on each trip so'll know if the loop is in the orginal order or not.)

So, on the very first trip out and back, you point to a as the node being tested and record b as what it points to. The next time out, if you find that a does not point to b anymore, then a is the first node in the cycle. Otherwise, on that same trip out, you shift to b as the node being tested and record what it points to, etc. until you find the start of the loop. And using the boolean you can know which way to leave the pointers when you break the cycle.

O(n^2) time unfortunately, but it kept the memory down anyway.