(간단한 코드)리트코드 141. Linked List Cycle

 

이번 문제는 연결 리스트에 "싸이클"이 존재하는지 판단하는 문제이다. 

여기서 사용하는 방법은 two pointer과 유사한 방법으로 할 것인데, 한칸씩 뒤로 가는 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:
        
        slow = fast = head 
        
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

            if slow == fast:
                return True
        
        return False

 

우선 slow와 fast 둘다 출발점은 같기 때문에 slow = fast = head라고 하고

while문을 돌린다.

여기서 알아야 하는 점은 만약에 싸이클이 존재하는 연결 리스트라면, slow와 fast는 무조건 만나게 되어있다.

 

그런데 만나지 못했다면, 이는 싸이클이 존재하지 않았고, fast는 빠르게 연결리스트의 마지막 노드에 도달하는 것을 의미한다.

fast가 마지막 노드에 도달하면, while문은 멈추게 되며, 마지막 줄에 있는 False를 반환하게 된다.