LeetCode 141. Linked List Cycle

주어진 Linked List가 순환한다면 True, 순환하지 않는다면 False를 반환하는 문제이다.

풀이

def hasCycle(self, head: Optional[ListNode]) -> bool:
    if not head or not head.next:
        return False

    slow = head
    fast = head.next
    while slow != fast:
        if fast is None or fast.next is None:
            return False

        slow = slow.next
        fast = fast.next.next
    return True

slow, fast 포인터를 사용하였다.

가장 먼저 head가 없거나 노드가 한 개일 경우는 cycle이 성립할 수 없으므로 False를 반환해 준다.

 

slow = head ,  fast = head.next로 설정한 뒤 while slow != fast:(slow와 fast가 만날 때까지 반복)을 사용해 준다.

만약 fast가 없거나 다음 노드가 없으면 False를 반환해 주고, slow와 fast가 만나서 while 문이 종료된다면 cycle이 성립되어 둘이 만난 것이므로 True를 반환해 준다.

결과값