List(싸이클탐지): 141. Linked List Cycle

141. Linked List Cycle

 

https://youtu.be/gBTe7lFR3vc?si=VAfWxrUDCliFGt2Q

 

# 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:
        # 연결 되어 있으면, fast 루프랑 slow 루프는 만날것이다 라는 아이디어
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True

        return False

 

싸이클 탐지 차원

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        visited = set()  # 해시맵 대신 집합 사용

        current = head
        while current:
            if current in visited:  # 이미 방문한 노드라면 싸이클 존재
                return True
            visited.add(current)
            current = current.next

        return False  # 리스트의 끝에 도달하면 싸이클 없음