List(싸이클탐지): 142. Linked List Cycle II

142. Linked List Cycle II

 

이 문제는 Linked List Cycle Detection 문제 중 하나로,

**Floyd's Cycle Detection Algorithm (Tortoise and Hare)**를 활용하여 해결할 수 있습니다.

아래는 단계별 풀이 방법입니다.

---

1. Floyd’s Cycle Detection Algorithm

• 두 포인터(Tortoise와 Hare)를 사용하여 Linked List를 순회합니다.
• 속도 차이를 이용해 두 포인터가 같은 노드에 도달하면 사이클이 있음을 확인할 수 있습니다.
• 사이클이 발견되면, 사이클의 시작 노드를 찾는 추가 작업을 수행합니다.

---

2. 단계별 풀이

1단계: 사이클 존재 여부 확인

1. slow 포인터는 한 번에 한 노드씩 이동합니다.
2. fast 포인터는 한 번에 두 노드씩 이동합니다.
3. 두 포인터가 만나면 사이클이 존재합니다.
4. 만약 fast 또는 fast.next가 None에 도달하면 사이클이 없습니다.

2단계: 사이클의 시작 노드 찾기

1. 사이클이 있음을 확인한 후, slow 포인터를 head로 되돌립니다.
2. slow와 fast를 각각 한 칸씩 이동하며 다시 만나는 지점을 찾습니다.
3. 두 포인터가 만나는 지점이 사이클의 시작 노드입니다.