[LeetCode] 141. Linked List Cycle

📌 Problem

[LeetCode] 141. Linked List Cycle

📌 Solution

Solution 1: visited()

Idea

• Traverse the linked list node by node
• Store each visited node in a set
• If a node is encountered again, a cycle exists
• If traversal reaches None, there is no cycle

Code

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

        while cur:
            if cur in visited:
                return True
            visited.add(cur)
            cur = cur.next

        return False

Complexity

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$ (due to the visited set)

⚠️ Why this is not optimal
This approach requires additional memory to store visited nodes. The problem can be solved using Floyd’s cycle detection algorithm with $O(1)$ extra space, which is generally preferred in interviews.

⭐️ Solution 2: Floyd’s Cycle Detection (Fast & Slow Pointers)

Idea

• Use two pointers starting at the head of the list
• Move slow one step at a time
• Move fast two steps at a time
• If a cycle exists, the two pointers will eventually meet
• If fast reaches the end (None), there is no cycle

Floyd's Cycle Detection Algorithm
연결 리스트에서 사이클이 존재하는지 판단하는 대표적인 알고리즘

핵심 아이디어는 다음과 같다:
두 개의 포인터를 사용해 연결 리스트를 순회한다.

• slow 포인터: 한 번에 1칸 이동
• fast 포인터: 한 번에 2칸 이동

만약 리스트에 사이클이 없다면, fast가 먼저 None에 도달하며 탐색이 종료된다.
반대로 사이클이 존재한다면, fast가 slow를 결국 추월하여 같은 노드에서 만나게 된다.

Code

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

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

            # If slow and fast meet, a cycle exists
            if slow == fast:
                return True

        # fast reached the end -> no cycle
        return False

Complexity

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$