[LinkedLists: Fast and Slow Pointers] 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  # 리스트의 끝에 도달하면 싸이클 없음

 

최종 코드

 

내 기존 코드: 잘못 됬음

# 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:
        if not head:
            return False

        visit = set()
        cur = head

        while cur:
            if cur.val in visit:
                return True
            visit.add(cur.val)            
            cur = cur.next
        return False

 

지금 작성하신 코드는 거의 맞는 방향이지만,
cur.val을 visit에 저장하고 비교하는 부분이 문제예요. ⚠️

---

❌ 왜 cur.val로 하면 안 될까?

노드의 값(val)은 중복될 수 있기 때문이에요!

• 예: 값이 3인 노드가 여러 개 있을 수 있는데
  그게 사이클인지, 그냥 값이 같은 건지 구분이 안 돼요.

---

✅ 어떻게 고쳐야 할까?

노드의 값(val)이 아니라,
노드 **자체의 메모리 주소 (즉, 객체)**를 기준으로 비교해야 해요!

파이썬에서는 ListNode 자체를 set에 저장하면 주소를 기준으로 비교할 수 있어요.

 

노드 자체 (cur)를 set에 저장하고 비교하기

# 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:
        if not head:
            return False

        visit = set()
        cur = head

        while cur:
            if cur in visit: # 노드 자체를 기준으로 비교
                return True
            visit.add(cur)            
            cur = cur.next
        return False

 

fast/slow 포인터(Floyd 알고리즘) 사용해서 공간 없이 사이클 감지

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

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

 

 

• slow는 한 칸씩, fast는 두 칸씩
• 만약 사이클이 있으면 언젠가는 반드시 만나요!