[2024] 3/6 Leetcode Daily Challenge 141. Linked List Cycle

141. Linked List Cycle

코드

해설

while fast and fast.next:

연결 리스트가 순환(cycle)일 경우 현재 노드(fast)와 그 다음 노드(fast.next)가 null이 되는 경우가 없다. 연결 리스트가 순환일 경우 항상 다음 노드가 존재하기 때문이다.
그러므로 해당 while문을 만족하지 못하면 False를 return 한다.

slow = slow.next
fast = fast.next.next

투 포인터 알고리즘을 사용하여 slow는 1칸, fast는 2칸씩 순회하도록 한다.

if (slow == fast):
	return True

slow 포인터와 fast 포인터가 만나는 지점이 존재 = 순환 연결 리스트
다음 조건에 해당할 경우 True를 return 한다.

자료 구조

• 연결 리스트(Linked list)

알고리즘

• 투포인터(Two pointer)

시간 복잡도

O(n)