Month: November 2007

그래프에서 cycle 판명법?

문제는 정말 간단하다. 답변도 만만치 않게 간단하다.

그런데 뭔가 해탈을 주는듯한 그런 문제일까나 ㅎㅎ

        

엄청나게 긴 linked list가 있다. 여기서 cycle을 어떻게 찾을 수 있을까?

 답은 간단하다. pointer 2개를 만드는데, 하나는 0에 위치하고 하나는 1에 위치한다. 그리고, 전자의 것은 1칸씩, 후자의 것은 2칸씩 뛰게 해서 둘이 만나면 싸이클이다.