Leetcode Python - 141. Linked List Cycle

Leetcode #141 - Linked List Cycle

이제 blind 75 leetcode를 풀어보겠습니다. https://leetcode.com/discuss/interview-question/460599/Blind-75-LeetCode-Questions

리트코드의 문제 141 ‘Linked List Cycle’을 파이썬으로 풀어 보도록 하겠습니다. 포인트는 slow와 fast node를 두어서, fast는 2칸씩, slow는 1칸씩 이동하면서 만난다면 순회, none이 나온다면 비순회를 정의하면 됩니다.

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

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

시간복잡도는

• O(n) : 한번의 while 문으로 None이 나올때까지 진행

공간복잡도는

• O(1) : listNode 변수 slow, fast 생성