[Python] 141. Linked List Cycle

난이도 : easy

 

head라는 linked list에서 cycle을 구성한다면 True를 return하는 문제

 

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

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

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

1. slow, fast 포인터를 모두 head로 초기화
2. 리스트의 끝에 도달할 때까지 반복
3. slow는 한 칸씩, fast는 두 칸씩 이동하고, 위치가 리스트의 끝인지 확인
4. slow와 fast가 만나면, 순환되는 중이기 때문에 True return
5. 순환이 없는 경우 False return

Runtime : 47ms (63.07%)

Memory : 19.87MB (47.52%)