728x90
링크드리스트에 사이클이 있는지 없는지 판단하는 문제이다.
set을 이용하여 간단히 풀 수도 있지만,
플로이드의 순환 찾기 알고리즘, 플로이드의 토끼와 거북이 알고리즘으로도 풀 수 있는 재밌는 문제였다!
풀이1. set 이용
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
seen = set()
cur = head
while cur:
if cur in seen:
return True
seen.add(cur)
cur = cur.next
return False링크드리스트를 한번 순회하므로 시간복잡도 O(n),
최대 n 크기의 set()을 사용하므로 공간복잡도 O(n)이다.
풀이2. 플로이드의 토끼와 거북이 알고리즘
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False링크드리스트에 사이클이 존재하면,
한 칸씩 이동하는 포인터와 두 칸씩 이동하는 포인터를 만들었을 때
두 포인터가 만나게 된다.
그렇지 않으면 더 빠른 노드가 끝에 도달하여 while문이 종료되게 된다.
리스트를 한번 순회하므로 시간 복잡도는 O(n),
두 개의 포인터만 필요하므로 공간 복잡도는 O(1)이다.
728x90
