LeetCode 문제 141. Linked List Cycle의 Python에서의 해답 예입니다.
h tps : // / ㅇ t 여기. 코 m / p 로b ㎇ ms / ㄱ 케 ぃ st cyc ぇ /

문제 개요

문제문은 간단하고 연결 목록이 주어지면 그것이 사이클(순환)을 가질지 어떨지를 결정하라(Given a linked list, determine if it has a cycle in it.)라는 문제입니다.
인수는 연결 목록(Linked List)입니다.

해결 방법

풀 때 알고리즘은 간단합니다. 여기에서는 예로서 문제문의 Example 1.로 생각해 봅시다.
첫째, 문제의 그래프 (고등학교 수학까지의 그래프가 아니라 데이터 구조로서의 그래프와 비슷하기 때문에 여기에서는 그래프라고합니다)입니다.



여기서 slow pointer와 fast pointer를 생각해 봅시다. 시작점은 여기에서 가장 왼쪽 3입니다. 느린 포인터는 한 번에 하나씩, 패스트 포인터는 한 번에 두 번 진행합니다. 자, 여기서 한 번 진행하면 아래 그림과 같이 됩니다.



이어서 2회 진행한 후는 아래 그림과 같이 됩니다.



3회 진행한 후에는 아래 그림과 같이 됩니다.



이 세 번 진행한 시점에서, slow pointer와 fast pointer가 같은 장소(노드 4)에 왔습니다.

해답 예

아래에서 답을 2개 올립니다.

해답 예 1

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        """
        type head: ListNode
        return type: bool
        """

        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

해답 예 1의 실행 결과는 다음과 같습니다. 이 시점에서 Python3에서 제출한 평균보다 64.54% 빠른 것 같습니다. 마찬가지로 메모리 사용량은 그보다 100% 적은 것 같습니다.

해답 예 2

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        """
        type head: ListNode
        return type: bool
        """

        try:
            slow = head
            fast = head.next
            while slow != fast:
                slow = slow.next
                fast = fast.next.next

            return True
        except:
            return False

해답 예 2의 실행 결과는 다음과 같습니다. 이 시점에서 Python3에서 제출한 평균보다 33.8% 빠른 것 같습니다. 마찬가지로 메모리 사용량은 그보다 100% 적은 것 같습니다.
해답예 1보다 처리 속도가 느린 것은, try except가 매회 판정 처리를 하고 있어, if문이 1개 늘어난 형태가 되기 때문에 그만큼 늦어져 있는 것이 원인이라고 생각됩니다.