LinkedList : Linked List Cycle

https://leetcode.com/problems/linked-list-cycle/

Linked List Cycle - LeetCode

 

slow pointer와 fast pointer를 이용해 해결한다.

slow pointer는 한칸씩 전진시키고

fast pointer는 두칸씩 전진시킨다.

만약 싸이클이 있다면 두 포인터는 언젠가 만나게된다.

두 포인터가 만나지 못한다면 싸이클이 없는거다.

시간복잡도는 O(N)

공간복잡도는 O(1)

 

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head

        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                return True
        
        return False