사이클 감지하기

leetcode 141. Linked List Cycle 문제풀이

문제: 주어진 연결리스트에 사이클이 있다면 true를 없다면 false를 반환하라

1. 각 노드를 set에 추가해가며 순회한다.

2. 다음에 순회할 노드가 이미 set에 들어있다면 true를 반환.

3. 순회를 무사히 마쳤다면 사이클이 없는 것이므로 false를 반환.

모든 노드를 set에 저장하려면 O(N)공간이 필요하다.

set에 노드를 저장하는 것 대신, 노드의 val값에 이미 방문했음을 표시한다면 메모리를 아낄 수있다.

투 포인터 테크닉을 활용해서도 공간복잡도를 O(1)으로 제한할 수 있다.

투 포인터 테크닉은 한 포인터는 더 빠르게 또 다른 포인터는 더 느리게 움직이도록하는 테크닉을 말한다.

위 코드에서 느린 포인터는 거북이(turtle) 빠른 포인터는 토끼(rabbit)로,

토끼는 거북이보다 한 스텝 빠른 위치에서 시작하여 2발자국씩 움직이고 거북이은 1발자국씩 움직인다.

만약 사이클이 존재한다면 거북은 결국 토끼를 만나게된다. 둘이 만난다면 true를 반환하고,

둘이 만나지않고 토끼가 먼저 결승점에 도착한다면 false를 반환하면 된다.

사례1. 만약 거북이가 토끼보다 한 발자국 앞서있다면,
그 다음 단계에서 토끼는 두 발 앞 거북이는 한 발 앞으로 나가 둘이 만나게 된다.

step 1 : [ 토끼, 거북이, # ]

step 2 : [ #, #, 토끼와 거북이 ]

사이클이 존재할 경우 토끼와 거북이는 결국 사례1에 수렴할 것이므로, 사이클이 존재할 때 둘은 언젠가 만나게된다.

step 1 : [ #, 거북이, #, 토끼 ]

step 2 : [ #, 토끼, 거북이, # ]

step 3 : [ #, #, #, 토끼와 거북이 ]

step 1 : [ 토끼, #, #, #, #, 거북이 ]

step 2 : [ 거북이, #, 토끼, #, #, # ]

step 3 : [ #, 거북이, #, #, 토끼, # ]

step 4 : [ 토끼, #, 거북이, #, #, # ]

step 5 : [ #, #, 토끼, 거북이, #, # ]

step 5 : [ #, #, #, #, 토끼와 거북이, # ]

hon9g