Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

Loop Detection

problem

Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop.

how to solve

If I can use extra space, I can solve this very easily. I can justly use a hash table to detect if the element is appeared or not.

Next, I want to consider this problem without using that data structure. I took the following steps.

  • Create two pointers, FastPointer and SlowPointer.
  • Move fastPointer at a rate of 2 steps and SlowPointer at a rate of 1 step.
  • When they collide, move SlowPointer to LinkedListHead. Keep FastPointer where it is.
  • Move Slow Pointer and FastPointer at a rate of one step. Return the new collision point

code1

without using extra space.

code2(with using map)

with using hash map.

Remove all ads