141. Linked List Cycle

원문: https://doljae.tistory.com/107

[Linked List Cycle - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com](https://leetcode.com/problems/linked-list-cycle/)

1. Object id값과 집합을 이용한 풀이

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        id_set = set()
        cur = head
        while cur:
            if id(cur) not in id_set:
                id_set.add(id(cur))
            else:
                return True
            cur = cur.next
        return False

객체 id값은 고유하기 때문에 집합에 넣고 이미 현재 객체 id값이 집합에 있다면 사이클이 있음으로 판단한다.

2. Floyd의 순환 알고리즘

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

시간 복잡도나 공간 복잡도가 별 차이 나진 않지만 이렇게도 풀 순 있다.