연결리스트 사이클이 시작되는 노드 찾기

leetcode 142. Linked List Cycle II 문제풀이

문제: 주어진 연결리스트에서 사이클이 없다면 null을, 있다면 사이클이 시작되는 노드를 반환하라.

 

1. 주어진 노드를 Hash Set에 추가하면 순회한다.

2. 이미 Hash Set에 있는 노드를 만나면 사이클이 시작된 것이므로 해당 노드를 반환한다.

3. 무사히 순회를 끝냈으면 사이클이 없는 것 이므로, null을 반환한다.

 

 

141번 사이클 감지하기 문제에서 활용한 투 포인터 테크닉을 활용하여 공간을 O(1)만큼만 사용할 수 있다.

leetcode 141. Linked List Cycle 사이클 감지하기

141번에서는 한 발자국씩 이동하는 포인터와 두 발자국씩 이동하는 포인터를 이용해, 사이클 내에 있는 아무 노드를 찾아내도 무관했다면, 이번 문제에서는 사이클이 시작되는 노드를 찾아야한다는 점이 다르다.

 

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

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

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

 

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

 

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

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

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

 

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

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

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

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

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

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

 

141번 처럼 토끼와 거북이 테크닉으로 교차점을 찾은 이후에 발견한 교차점과 head 노드를 이용해 사이클이 시작되는 노드를 찾을 것이다. C는 사이클 내에 있는 노드의 수, F는 사이클 이전에 있는 노드의 수라고 했을 때. 사이클내에 있는 노드는 순서대로 0부터  C-1까지의 값으로, 사이클 이전의 노드는 -F부터 -1까지의 값으로 나타내도록 하겠다.

 

-3, -2, -1, [ 0, 1, 2, 3, 4 ]

 

step 0 : 토끼와 거북이, -2, -1, [ 0, 1, 2, 3, 4 ]

step 1 : -3, 거북이, 토끼, [ 0, 1, 2, 3, 4 ]

step 2 : -3, -2, 거북이, [ 0, 토끼, 1, 3, 4 ]

step 3 : -3, -2, -1, [거북이, 1, 2, 토끼, 4]

 

거북이가 F만큼 이동해서 위치 0에 도달햇을 때, 토끼는 2F만큼 이동해서 위치 h = F + F % C인 3 에 도달해 있다. 토끼는 사이클이 시작되는 노드로부터 C - h인 5 - 3 = 2만큼 떨어져있다.

C- h = 5 - 3 = 2 스텝 뒤, 거북이는 C- h인 2에 위치할 것이고, 토끼는 h + 2(C-h) = 2C - h 를 %C 한 곳에 위치할 것이다. 값을 대입해서 풀어보자면, (2*5 - 3)%5 = 2 2C - h 로 거북이와 같은 노드에서 만난다.

 

step 4 : [ 토끼, 거북이, 2, 3, 4 ]

step 5 : [ 0, 1, 토끼와 거북이, 3, 4 ]

 

 

이렇게 토끼와 거북이가 교차하는 노드를 찾았다. 하지만 이 노드는 사이클이 시작하는 곳은 아니다.

사이클이 시작하는 곳을 찾기 위해 리스트의 첫 노드와 토끼와 거북이의 첫 교차점을 똑같은 속도로 순회할 것이다. 

 

step 0 : 헤드, -2, -1, [ 0, 1, 첫 교차점, 3, 4 ]

step 1 : -3, 헤드, -1, [ 0, 1, 2, 첫 교차점, 4 ]

step 2 : -3 -2, 헤드, [ 0, 1, 2, 3, 첫 교차점, ]

step 3 : -3, -2, -1, [헤드와 교차점, 1, 2, 3, 4 ]

 

헤드노드가 F+1만큼 이동해 사이클이 시작하는 곳에 도달했을 때 첫 교차점 노드와 만나게된다. 어떻게 이게 가능한 걸까? 이는 F = b이기 때문이다.

 

F = 사이클이 존재하지 않는 부분의 길이

a = 첫 교차점의 위치

b = 사이클의 길이 - 첫 교차점의 위치

일때,

 

2 * 거북이가 이동한 거리 = 토끼가 이동한 거리

2(F+a) = F + a + b + a

2F + 2a = F + 2a + b

F = b

 

 

Tortoise and Hare algorithm 남생이와 산토끼 알고리즘..?이 맞는 명칭이지만,

나는 rabbit and turtle이 토끼와 거북이 우화를 연상하는데 더 직관적이여서 변수명을 rabbit과 turtle로 사용했다.