141. Linked List Cycle ☆★★

141. Linked List Cycle

# 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

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

 

좋습니다! 지금 아이디어는 **플로이드의 사이클 탐지 알고리즘 (Floyd's Cycle Detection Algorithm)**을 잘 반영하고 있는데,

한 가지 중요한 버그가 있습니다.

---

❌ 문제점

while slow and fast:

• fast = fast.next.next 를 하기 때문에, fast와 fast.next가 모두 존재하는지 확인하지 않으면 NoneType 에러가 발생할 수 있어요.

---

✅ 수정해야 할 부분

while fast and fast.next:

• 이렇게 해야 fast.next.next를 안전하게 접근할 수 있습니다.

 

1차 수정 버전

# 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

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

 

지금 코드 구조는 거의 완벽한데, if slow == fast: 조건이 너무 일찍 실행되고 있어서 문제가 생깁니다.

---

🔍 왜 안 되냐면?

slow = fast = head
while fast and fast.next:
    if slow == fast:  # ❗첫 루프부터 slow == fast 이므로 바로 True 반환됨
        return True
    ...

• slow와 fast가 처음에 같은 head를 가리키기 때문에 루프 시작 전에 같은 노드를 비교하게 되어 무조건 True가 나올 수 있음, 특히 사이클이 없는 경우에도.

---

✅ 해결 방법

slow와 fast가 처음 이동한 후에 비교해야 합니다.

 

최종 코드

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가 항상 같으니까 비교 먼저 하면 안 됩니다!

# 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

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            """
            while 전에 
            slow = fast = head 초기화 하므로,

            slow = slow.next
            fast = fast.next
            이 로직 전에 
            if slow == fast 체크하면 바로 while 빠져나옴
            """
            if slow == fast: # 싸이클이 있으면
                return True
        return False