Linked List Cycle

https://leetcode.com/problems/linked-list-cycle/?envType=study-plan-v2&envId=top-interview-150

문제

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

풀이

• 주어진 링크드 리스트에 사이클이 있는지 확인하는 문제
• 사이클은 시작 노드에서 next를 계속 탐색하다가 다시 시작 노드를 가리키게 되는 경우를 말한다.
• visited set을 생성하여 방문한 노드들을 추가한다.
  • 만약 현재 노드가 visited에 있다면 사이클이 존재한다는 뜻이므로 True 리턴
  • 그외에는 visited에 노드를 추가하고 head = head.next로 이동
• while문 동안 발견하지 못했다면 사이클이 존재하지 않는 경우이므로 return False

Solution(Runtime: ms)

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

        while head:
            if head in seen:
                return True
            seen.add(head)
            head = head.next
        
        return False