It's enough to use one (slow) pointer and "visited" set. Visited requires O(n) space but also detects any loops. We just need to clear the set every time the direction changes.

It's enough to walk at most (N + 1) steps because one of the following will happen:

• detected a cycle with the same direction (i.e. returned "true")
• entered a cycle with direction change. This is the only logical option after N + 1 steps if the above didn't hold, since we have to step at the same node at least once.