Notice
Recent Posts
Recent Comments
Link
오늘도 개발
31. Linked List Cycle 본문
문제
연결 리스트에 사이클이 있으면 True, 없으면 False를 반환하시오.
해결 방식
연결리스트를 한 칸씩 가며 탐색하는 slow 포인터와
두 칸씩 이동하며 탐색하는 fast 포인터 설정.
사이클이 있으면 fast 포인터가 slow 포인터와 언젠가 일치할 것.
사이클이 없으면 next가 None인 노드가 있을 것 => fast 포인터가 언젠가 None을 가리킬 것.
fast 포인터와 slow 포인터가 일치하면 True 반환.
fast 포인터가 None을 가리키면 False 반환.
def hasCycle(head):
fast = head
slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if slow == fast:
return True
return False'자료구조 & 알고리즘 > Leetcode' 카테고리의 다른 글
| 33. Intersection of Two Linked Lists (0) | 2022.10.21 |
|---|---|
| 32. Linked List Cycle II (0) | 2022.10.20 |
| 30. Design Linked List (0) | 2022.10.19 |
| 28. Rotate Array (0) | 2022.10.17 |
| 27. Minimum Size Subarray Sum (0) | 2022.10.15 |