[Algorithm] 토끼와 거북이 - 1

LeetCode 141번 문제 - Linked List Cycle

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

- 입력: 연결 리스트의 head
- 출력: 사이클이 있으면 true, 없으면 false를 리턴
- 공간을  O(1)만 사용하고 풀기
- 그냥 푸는 건 easy인데, O(1) 메모리를 사용해서 푸는 건 간단하지 않음
- 위키피디아의 Cycle detection (순환 검출) 을 참고하면 자세히 나와 있음

---

 토끼와 거북이 알고리즘 1 - 사이클 유무 판단

- 토끼와 거북이는 같은 장소에서 출발

- 거북이가 한 칸을 이동할 동안, 토끼는 두 칸 이동
- 만약 연결 리스트 내에 사이클이 없다면 토끼와 거북이는 이동 중에 NULL 노드를 만날 것
- 만약 연결 리스트 내에 사이클이 있다면 토끼와 거북이는 언젠가 반드시 만나게 될 것

class Solution:
	def hasCycle(self, head: ListNode) -> ListNode:
	"""
	ListNode: 연결 리스트의 노드를 나타내는 클래스, 각 노드는 값과 다음 노드를 가리키는 포인터 가짐
	hasCycle: 사이클을 확인하는 메서드, `head` 라는 연결 리스트의 헤드 노드를 매개 변수로 받고
	해당 연결 리스트가 사이클을 가지면 사이클의 시작 노드 반환
	사이클이 없으면 `None` 반환
	`self`는 현재 인스턴스를 가리키는 참조로, 클래스 내의 다른 메서드와 속성에 접근할 수 있게 함
	클래스 내부에서 메서드 정의할 시 첫 번째 매개변수로 `self`를 선언해야 함
	"""
		hare = tortoise = head	# 토끼와 거북이를 같은 출발선에 둠
		while hare != None and tortoise != None:	# 둘 다 None이 아니라면
			if hare.next == None:	# 사이클이 없다면 NULL 노드를 만날 것
				return False
			hare = hare.next.next	# 사이클이 있다면 두 칸 이동
			tortoise = tortoise.next	# 거북이는 한 칸 이동
			if hare == tortoise:		# 만약 거북이와 토끼가 만났다면
				return True
			return False

---

Floyd's tortoise and hare algorithm

- 서로 다른 속도로 움직이는 두 개의 포인터를 이용해서 O(n) 시간 복잡도, O(1) 공간 복잡도로 Cycle Detection Problem을 해결하는 알고리즘
- 간단하지만 강력한 알고리즘

---

출처

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