[Leetcode] 141. Linked List Cycle

문제 바로가기
hash set에 각 node의 id를 저장하며 탐색하다가 이미 탐색한 node 방문시 true를 반환한다.
기존의 node의 val이나 next를 수정하면 추가 저장 공간을 $O(1)$으로 줄일 수 있으나, 함수 내에서 전달받은 데이터를 수정하지 않는 것이 맞다고 생각되어 사용하지 않았다.

Hash Set

Time Complexity: $O(n)$
Space Complexity: $O(n)$

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

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

Floyd cycle detection

fast는 한 iteration에서 slow 1 node더 많이 움직인다. 때문에 cycle이 존재한다면 slow가 모든 node를 순회하기 전에 slow와 fast는 같은 node를 가리키는 순간이 올 것이다.
Time Complexity: $O(n)$
Space Complexity: $O(1)$

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