Leetcode Python - 114. Linked List Cycle

Leetcode #114 - Linked List Cycle

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. linkedlist를 집중적으로 풀어보겠습니다.

리트코드의 문제 114 ‘Linked List Cycle’을 파이썬으로 풀어 보도록 하겠습니다.

discuss를 보도록 하겠습니다…

포인트는 slow와 fast를 두어서 slow는 한칸씩, fast는 두칸씩 전진하면 cycle의 경우 언젠가는 만난다는 것이 포인트입니다.

전체 코드는 아래와 같습니다.

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

시간복잡도는 O(n) : fast가 두칸씩 가므로 n/2만큼 수행

공간복잡도는 O(1) : slow와 fast의 포인팅