[Algorithm] 토끼와 거북이 - 2

LeetCode 142번 문제 - Linked List Cycle 2

https://leetcode.com/problems/linked-list-cycle-ii/

주어진 연결 리스트에서 사이클의 시작 노드 찾기
- 입력: 연결 리스트의 head
- 출력: 사이클이 있으면 시작 노드, 없으면 null 리턴

- 토끼와 거북이 알고리즘으로는 만나는 거까진 알 수 있었는데 시작을 어디서 했는지는 모름

---

 토끼와 거북이 알고리즘 2 - 시작 위치 찾기

1. 토끼와 거북이는 같은 장소에서 출발
2. - 거북이가 한 칸을 이동할 동안, 토끼는 두 칸 이동
3. 만약 연결 리스트 내에 사이클이 없다면 토끼와 거북이는 이동 중에 NULL 노드를 만날 것
4. 만약 연결 리스트 내에 사이클이 있다면 토끼와 거북이는 언젠가 반드시 만나게 될 것
5. 토끼와 거북이가 만나면 거북이는 그 자리에 있고, 토끼는 출발선상에 다시 섬
6. 이 때부터는 같은 속도로 토끼와 거북이가 한 칸씩 이동
7. 토끼와 거북이가 다시 만나는 위치의 노드(사이클 시작 노드)를 리턴

class Soultion
	def detectCycle(self, head: ListNode) -> ListNode:
		# Phase 1: Detecting the cycle
		hare = tortoise = head
		where hare != None and tortoise != None:
			if hare.next == None:
				return None
			hare = hare.next.next
			tortoise = tortoise.next
			if hare == tortoise:	 # 토끼와 거북이가 만나면
				# Phase 2: Finding the starting position
				hare = head	# 토끼를 출발 위치로 보내고
				while hare != tortoise:
					hare = hare.next	# 토끼 1칸 이동
					tortoise = tortoise.next	# 거북이 1칸 이동
				return hare	# 시작 노드 리턴
		return None

---

토끼와 거북이 알고리즘 3 - 사이클 길이

1. 사이클의 시작점에 토끼와 거북이 존재
2. 토끼만 한 칸씩 이동하며 길이 측정
3. 토끼가 거북이 자리에 오게 되면 2번 과정 멈춤
4. 그 때의 길이가 사이클의 길이가 됨

---

출처

1. 주나온TV 아무거나연구소 - https://www.youtube.com/watch?v=WBoIL7_Xnmc&list=PLHqxB9kMLLaNIvuYT6NgXsIt782lS3xiD&index=2